OI题库

【题目描述】

这是一道关于两个人的题目，我们不妨叫他们Alice和Bob。Alice画了一个凸n边形，顶点用1～n按任意顺序标号。然后她在多边形中画了一些不相交的对角线（但它们有可能在凸多边形的顶点处相交）。她告诉Bob这些边和对角线，但不告诉他哪些是边哪些是对角线。每一条边和对角线用其两个端点描述。Bob必须猜出多边形顶点的顺序。帮助他解决这个问题。

例如，如果n=4并且Alice给出了（1，3），（4，2），（1，2），（4，1），（2，3）五条边，则多边形顶点一个可能的顺序是1，3，2，4.

【输入格式】

输入包含多组数据。

输入文件的第一行有一个正整数d代表数据组数，1<=d<=20.接下来是d组数据。

每组数据是连续的两行。

第一行有两个空格隔开的整数n,m，3<=n<=10000,0<=m<=n-3.n是多边形的顶点数，m是对角线的数量。

接下来的一行有2(m+n)个空格隔开的整数，即所有边和对角线的两个端点。第2j-1个数和第2j（1<=j<=m+n）个数分别是aj和bj（1<=aj<=n,1<=bj<=n），代表一条边或对角线的两个端点是aj,bj。边和对角线可能会按照任意顺序给出，并且没有重复。

Alice不会作弊，即一定有解。

【输出格式】

每组数据输出一行，共d行。

第i行包含n个由空格隔开的整数，是一个1～n的排列，代表第i组数据中多边形的顶点顺序。这个序列应当从1开始，接下来是1号顶点编号最小的相邻顶点。

【样例输入】

1

4 1

1 3 4 2 1 2 4 1 2 3

【样例输出】

1 3 2 4

【来源】

CEPC 2001 Problem A - Alice and Bob