문제
트리에 대해 공부하던 정올이는, 리프 노드(Leaf Node) 에 흥미를 갖기 시작했다.
리프 노드란, "연결된 간선의 개수가 정확히 1개" 인 노드를 의미한다.
예를 들어,
위 트리의 리프 노드는 1번, 5번, 6번 노드다.
2번 노드는 연결된 간선이 2개,
3번 노드는 연결된 간선이 3개,
4번 노드는 연결된 간선이 2개라서 리프 노드가 될 수 없다.
노드가 2개 이상인 트리에서, 리프 노드는 항상 2개 이상이다.
정올이는 리프 노드 중에서 2개를 선택하려고 한다.
단, 정올이는 고른 두 리프 노드 사이의 거리가 최소가 되게 하려고 한다.
정올이를 도와 어떤 두 리프 노드를 선택할지 구해보자.
입력
첫 줄에 트리의 노드 개수 N 이 입력된다. ( 2 ≤ N ≤ 2×105 )
이후 N - 1 줄에 걸쳐 간선의 정보가 X Y 형태로 입력된다. ( 1 ≤ X, Y ≤ N, X ≠ Y )
번호가 X 인 노드와 Y 인 노드가 간선으로 연결되어 있다는 뜻이다.
입력되는 그래프는 항상 트리가 된다.
출력
첫 줄에, 두 리프 노드 사이의 최소 거리를 출력한다.
두 번째 줄에, 이를 만족하는 두 리프 노드의 번호를 출력한다. ( 순서는 상관없음 )
( 답이 되는 경우가 2가지 이상이라면, 아무거나 출력해도 된다. )
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | 입력되는 트리의 리프 노드는 2개 뿐이다. |
| #2 | 20점 | 2 ≤ N ≤ 100 |
| #3 | 30점 | 입력되는 트리의 리프 노드는 20개 이하다. |
| #4 | 40점 | 제약 조건 없음 |
예제 #1
6
5 3
3 4
4 1
2 3
2 6
3
1 5
본문 예시 그림이다.
( 1 5 ) 대신 ( 5 1 ), ( 5 6 ), ( 6 5 ) 모두 가능하다.
예제 #2
8
1 2
2 3
2 4
4 5
4 6
6 7
7 8
2
1 3
( 1 3 ) 대신 ( 3 1 ) 도 가능하다.
로그인해야 코드를 작성할 수 있어요.