순찰 경로

시간 제한1초메모리 제한512 MB

요약

완전 그래프의 신장 트리가 주어질 때, 트리의 간선을 하나도 쓰지 않으면서 모든 정점을 한 번씩 지나는 해밀턴 경로를 찾거나 없으면 -1을 출력한다.

문제

ALPS시(市)는 $N$ 개의 건물과 $N(N-1)/2$ 개의 도로로 구성되어 있다. 각 도로는 서로 다른 두 건물을 연결한다. 동일한 도로가 여러 개 존재하지 않는다. 즉, 모든 도시는 서로 도로를 통해 직접적으로 연결되어 있다.

경비 용역 업체에 취직한 정휘는 매일 밤 각 건물을 정확히 한 번씩 방문해서 순찰해야 한다. 이때 정휘는 도로를 이용해서 다른 건물로 이동해야 하며, 도로를 통해 어떤 건물에 도착했다면 그 건물을 반드시 방문해야 한다.

ALPS시의 시장인 윤헌이는 도시의 교통 환경을 개선하기 위해 $N-1$ 개의 도로를 보수하려고 한다. 이때, 도시의 모든 사람들이 혜택을 누릴 수 있어야 하기 때문에, 보수된 도로만 사용해 모든 도시가 연결되도록 도로를 선택할 것이다.

보수 공사가 진행되는 도로는 순찰할 때 이용할 수 없다. 보수 공사가 진행되는 $N-1$ 개의 도로가 주어졌을 때, 공사가 진행되고 있는 도로를 이용하지 않고 모든 건물을 정확히 한 번씩 순찰하는 경로를 구해보자.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스마다, 첫째 줄에 건물의 개수 $N$ 이 주어진다.

이후 $N-1$ 개의 줄에 걸쳐, 각 줄에 공사 중인 도로가 연결하는 두 건물의 번호 $u\_i, v\_i$ 가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 정답을 출력한다.

모든 건물을 정확히 한 번씩 순찰하는 경로가 존재한다면 건물의 방문 순서를 차례대로 공백으로 구분해서 출력한다. 가능한 순찰 경로가 여러 가지라면 아무거나 출력해도 된다.

경로가 존재하지 않는 경우 $-1$ 을 출력한다.

예제 1

입력

예상 출력

-1
-1
2 4 1 3
4 1 5 2 3
6 1 4 5 3 2