| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 207 | 56 | 49 | 31.410% |
ALPS시(市)는 $N$개의 건물과 $N(N-1)/2$개의 도로로 구성되어 있다. 각 도로는 서로 다른 두 건물을 연결한다. 동일한 도로가 여러 개 존재하지 않는다. 즉, 모든 도시는 서로 도로를 통해 직접적으로 연결되어 있다.
경비 용역 업체에 취직한 정휘는 매일 밤 각 건물을 정확히 한 번씩 방문해서 순찰해야 한다. 이때 정휘는 도로를 이용해서 다른 건물로 이동해야 하며, 도로를 통해 어떤 건물에 도착했다면 그 건물을 반드시 방문해야 한다.
ALPS시의 시장인 윤헌이는 도시의 교통 환경을 개선하기 위해 $N-1$개의 도로를 보수하려고 한다. 이때, 도시의 모든 사람들이 혜택을 누릴 수 있어야 하기 때문에, 보수된 도로만 사용해 모든 도시가 연결되도록 도로를 선택할 것이다.
보수 공사가 진행되는 도로는 순찰할 때 이용할 수 없다. 보수 공사가 진행되는 $N-1$개의 도로가 주어졌을 때, 공사가 진행되고 있는 도로를 이용하지 않고 모든 건물을 정확히 한 번씩 순찰하는 경로를 구해보자.
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.
각 테스트 케이스마다, 첫째 줄에 건물의 개수 $N$이 주어진다.
이후 $N-1$개의 줄에 걸쳐, 각 줄에 공사 중인 도로가 연결하는 두 건물의 번호 $u_i, v_i$가 공백으로 구분되어 주어진다.
각 테스트 케이스마다 한 줄에 정답을 출력한다.
모든 건물을 정확히 한 번씩 순찰하는 경로가 존재한다면 건물의 방문 순서를 차례대로 공백으로 구분해서 출력한다. 가능한 순찰 경로가 여러 가지라면 아무거나 출력해도 된다.
경로가 존재하지 않는 경우 $-1$을 출력한다.
5 2 1 2 3 1 2 2 3 4 1 2 2 3 3 4 5 1 2 1 3 2 4 3 5 6 1 2 1 3 2 4 2 5 3 6
-1 -1 2 4 1 3 4 1 5 2 3 6 1 4 5 3 2