27381번 - 순찰 경로 스페셜 저지

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

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

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

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

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

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

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

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

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

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

• $1\leq T\leq 100\, 000$
• $2\leq N\leq 200\, 000$
• 모든 테스트 케이스에서 $\sum N\leq 200\, 000$
• $1\leq u_i<v_i\leq N$
• $u_i\neq v_i$
• $i\neq j$ 이면 $(u_i,v_i)\neq(u_j,v_j)$
• 모든 도시는 공사가 진행되는 $N-1$개의 도로만 사용해 서로 이동할 수 있음