앨리스와 밥

앨리스와 밥이 퍼즐을 푼다. 앨리스는 꼭짓점이 $n$개인 볼록 다각형을 그리고, 각 꼭짓점에 정수 $1, 2, \dots, n$을 임의의 순서로 붙인다. 이어서 서로 교차하지 않는 대각선 몇 개를 그린다(끝점을 공유하는 것은 교차로 보지 않는다).

앨리스는 다각형의 모든 변과 자신이 그린 대각선을 하나의 목록에 섞어서, 각각을 두 끝점만으로 알려 준다. 어느 것이 변이고 어느 것이 대각선인지는 알려 주지 않는다. 밥은 이 목록만 보고 다각형 경계를 따라가는 꼭짓점들의 순환 순서를 알아내야 한다.

다각형이 볼록이고 대각선이 서로 교차하지 않으므로, 경계 순서는 회전과 반사를 무시하면 유일하게 결정된다. 각 퍼즐에 대해 이 경계 순서를 복원하는 프로그램을 작성하라.

첫째 줄에 퍼즐의 개수 $d$가 주어진다($1 \le d \le 20$).

각 퍼즐은 두 줄로 주어진다.

• 첫째 줄에는 두 정수 $n$과 $m$이 주어진다($3 \le n \le 10\,000$, $0 \le m \le n - 3$). 각각 꼭짓점의 개수와 대각선의 개수이다.
• 둘째 줄에는 $n$개의 변과 $m$개의 대각선을 나타내는 $2(m + n)$개의 정수가 주어진다. $1 \le j \le m + n$인 각 $j$에 대해, $2j-1$번째와 $2j$번째 위치의 정수는 하나의 변 또는 대각선의 두 끝점 $a_j$와 $b_j$이며, $1 \le a_j, b_j \le n$이고 $a_j \ne b_j$이다.

변과 대각선은 임의의 순서로 주어지고 중복은 없다. 모든 퍼즐에는 항상 해가 존재한다.

정확히 $d$개의 줄을 출력한다. 각 퍼즐마다 한 줄씩 출력한다. $i$번째 퍼즐에 대해 $1, 2, \dots, n$의 순열을 출력하는데, 이는 다각형 경계를 따라 나타나는 꼭짓점들의 순서이다. 수열은 반드시 꼭짓점 $1$에서 시작해야 하며, 두 번째 원소는 꼭짓점 $1$의 두 경계 이웃 중 더 작은 쪽이어야 한다.