문제 설명
트리 구조란 그래프의 일종으로, 회로(Cycle)가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프다.
각 노드의 사이 거리는 1이라고 할 때, 위의 예제로 주어진 트리에서 가장 멀리 떨어져 있는 두 노드는 A와 B로, 그 거리의 값은 6이 된다. 여기서는 A-B말고도 거리가 6인 두 노드가 존재 하지만, 6보다 멀리 떨어져 있는 두 노드는 존재하지 않는다.
트리가 주어졌을 때, 가장 멀리 떨어져 있는 두 노드의 거리를 구하는 프로그램을 작성하라.
입력 설명
첫 줄에는 테스트 케이스의 수 T (1 <= T <= 100)가 주어진다.
각 테스트 케이스의 첫 줄에는 노드의 개수 N (2 <= N <= 10,000)이 주어지고, 그 밑에는 N-1줄의 연결된 두 노드의 번호 a, b(1 <= a, b <= N)가 공백으로 구분되어 주어진다.
모든 입력은 문제에 주어진 트리의 정의에 맞는 입력만 들어오고, 모든 노드는 하나의 트리를 이룬다.
각 테스트 케이스의 첫 줄에는 노드의 개수 N (2 <= N <= 10,000)이 주어지고, 그 밑에는 N-1줄의 연결된 두 노드의 번호 a, b(1 <= a, b <= N)가 공백으로 구분되어 주어진다.
모든 입력은 문제에 주어진 트리의 정의에 맞는 입력만 들어오고, 모든 노드는 하나의 트리를 이룬다.
출력 설명
각 테스트에서 가장 먼 두 노드의 거리의 값을 출력하라.
입력 예시 Copy
2
13
1 2
3 2
4 2
11 12
13 11
5 2
2 6
6 7
7 8
8 9
10 8
8 11
3
2 3
1 3
출력 예시 Copy
6
2