30070 - Alice and Bob

Alice 和 Bob 在玩一个游戏。Alice 画了一个有 n 个节点的凸多边形，凸多边形上的节点从 1 到 n 按任意顺序标号，然后她在凸多边形中画了几条不相交的对角线（公共点为节点不算相交）。她把每条边和对角线的端点标号都告诉了 Bob，但没有告诉他哪条是边、哪条是对角线。Bob 必须猜出节点顺（逆）时针的节点标号序列，任意一个符合条件的序列即可。

例如 n=5，给出的边或对角线是 (1,4)、(4,2)、(1,2)、(5,1)、(2,5)、(5,3)、(1,3)，那么一个可能的节点标号顺序为 (1,3,5,2,4)。

请编写程序，对每个测试用例进行如下处理：输入 Alice 对 Bob 给出的边和对角线的描述；计算在凸多边形的边上节点的顺序，输出结果。

输入的第 1 行给出一个正整数 d（1 \le d \le 20），表示测试用例的数目，然后给出若干测试用例。

每个测试用例由连续的两行组成。

测试用例的第 1 行给出两个整数，用一个空格分开，分别为凸多边形的节点数 n 和在凸多边形中画的对角线数 m，其中 3 \le n \le 10000、0 \le m \le n-3。

第 2 行给出 2(n+m) 个整数，整数间用空格分开，这些整数表示凸多边形的边和一些对角线的节点，例如，整数 a_j、b_j 分别在第 2j-1 和 2j 的位置上（1 \le j \le m+n，1 \le a_j \le n，1 \le b_j \le n，a_j \ne b_j），表示一条边或一条对角线的节点。边和对角线以任意顺序给出，不能重复。

本题设定解答是存在的。

输出 d 行，每行对应一个测试用例。

第 i 行给出 n 个整数 1, 2, \dots, n 的一个排列，也就是说，第 i 个测试用例给出凸多边形的边界上节点的顺序编号，序列从 1 开始，第二个元素为节点 1 的两个相邻节点中编号较小的节点。