[CEPC2001]爱丽丝和鲍勃

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file aliceandbob.in Output file aliceandbob.out

【题目描述】

这是一道关于两个人的题目,我们不妨叫他们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