두 트리

정점에 $1,2,\cdots,N$의 번호가 붙은 트리 $T_1$이 주어진다.

같은 정점들을 가지는 두 트리 $T_1,T_2$에 대해, 다음을 만족하는 정점들의 집합 $S$가 존재하지 않을 때 $T_1$과 는 에 있다고 하자.

• $2\le |S|\le N-1$.
• $T_1$에서 $S$가 유도하는 부분 그래프와 에서 가 유도하는 부분 그래프가 모두 연결되어 있다.

$T_1$과 좋은 관계에 있는 트리 $T_2$가 존재하는지 판정하고, 존재한다면 하나를 구성하라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 다음과 같이 출력한다.

조건을 만족하는 $T_2$가 존재하지 않으면 한 줄에 $-1$을 출력한다.

존재한다면 $N-1$개의 줄에 걸쳐 다음과 같이 출력한다.

• $1\le T\le 50\,000$.
• $3\le N\le 200\,000$.
• $1\le U_{}$ ().