시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB219847739.086%

문제

$1$부터 $N$까지 번호가 붙은 $N$개 정점으로 이루어진 두 개의 트리 $T_1$, $T_2$가 주어진다. 서로 다른 양의 정수 $s$, $e$에 대해 각 트리에서 $s$번 정점에서 $e$번 정점으로 가는 최단 경로를 생각하자. 두 트리에서 최단 경로를 이루는 정점들의 번호 순서가 완전히 동일할 때, 그 경로를 두 트리의 공통 경로(Common Path)라고 정의한다. 이때 공통 경로의 길이는 $s$번 정점과 $e$번 정점을 잇는 최단 경로에 포함되는 간선의 수이다.

두 트리에서 찾을 수 있는 공통 경로 중 가장 길이가 긴 것을 하나 찾는 프로그램을 작성하시오.

입력

첫째 줄에 $T_1$, $T_2$의 정점의 개수를 나타내는 양의 정수 $N$이 주어진다.

둘째 줄부터 $N-1$개 줄에 걸쳐 $T_1$를 구성하는 간선들의 정보가 주어진다. 각 줄에는 각 간선이 연결하는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다.

이어서 $N-1$개 줄에 걸쳐 $T_2$를 구성하는 간선들의 정보가 주어진다. 각 줄에는 각 간선이 연결하는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다.

출력

첫째 줄에 가장 긴 공통 경로의 양 끝 정점의 번호 $s$, $e$를 공백으로 구분하여 출력한다. 만약 가장 긴 공통 경로가 여러 개여도 하나만 출력하면 된다.

만약 길이가 $1$ 이상인 공통 경로가 존재하지 않는다면, -1을 출력한다.

제한

  • $2\leq N\leq 100\, 000$
  • $1\leq u,v\leq N$

서브태스크

번호배점제한
111

공통 경로가 존재할 경우, 길이가 반드시 1이다.

227

$N \leq 1000$

362

추가 제한 조건이 없습니다.

예제 입력 1

8
1 2
1 3
1 4
2 5
2 6
2 7
5 8
1 2
1 3
2 4
2 5
3 6
4 7
5 8

예제 출력 1

8 3

노트

트리는 사이클이 없는 연결 그래프이다.

출처

School > 서울과학고등학교 > SciOI 2025 C번

채점 및 기타 정보

  • 예제는 채점하지 않는다.