문제1256--간선 하나를 제거해 트리 만들기

1256: 간선 하나를 제거해 트리 만들기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

N개의 노드로 구성된 무방향 그래프가 주어집니다. 이 그래프의 간선 수는 N이며, 이 중 하나의 간선을 제거하면 트리가 됩니다. 주어진 간선 중 어떤 간선을 제거하면 트리가 되는지 찾아주세요. 여러 개 간선이 답이 될 수 있습니다. 이 경우 입력 중 가장 뒤에 나타나는 간선을 출력해 주세요.

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=1,000)가 주어집니다. 각 테스트케이스는 두 줄로 주어집니다. 첫 줄에는 그래프의 노드 수 N(3<=N<=1,000)이 주어집니다. 두 번째 줄에는 N개의 간선 정보가 주어집니다.  노드의 이름 L은 1부터 N까지 수로 주어집니다.

출력 설명

각 테스트케이스마다 하나의 간선을 제거하였을 때 트리가 되는 간선을 찾아주세요. 여러 간선이 있을 경우 입력에서 가장 뒤애 나타나는 간선을 출력해 주세요.

입력 예시 Copy

2
3
1 2 1 3 2 3
5
1 2 2 3 3 4 1 4 1 5

출력 예시 Copy

2 3
1 4