Preparing NOJ

pdf的旅游

1000ms 65536K

Description:

a协有一位pdf是一位旅(作)游(死)爱好者,曾经在出去比赛之后拐带学弟翘课一周,四处旅游。

最近pdf又突发奇想,想再出去旅游一次。出去旅游之前当然要好好计划一番。Pdf给自己想去的地方并给它们编好了号(起点为1)。为了不跟自己过不去,pdf提前找出哪些地点存在交通方便的路径,而且只会走这些路径。

为了旅途乐趣的最大化,pdf希望每个地点都到访过的同时,又保证来去都不会走重复的路,而且最终还要回到起点。问想要达到上述要求,pdf应该怎么样安排地点的访问顺序。

Input:

第一行一个整数t,表示数据组数。

每组数据的第一行两个整数nm分别表示地点数和路径数。(2≤n≤10,n≤m≤n(n-1)/2)

接下来的m行每行两个整数x表示xy之间交通方便。(保证两点之间只会有一条路)(1x,yn)

Output:

每组数据输出一行,从起点开始的游览顺序。以空格分隔开。如果存在多解,则输出字典序最小的路径。(除起点外每个点只能访问一次)


Sample Input:

2
4 4
1 3
2 3
2 4
1 4

5 7
1 4
1 5
4 2
5 3
3 2
5 4
2 1

Sample Output:

1 3 2 4 1
1 2 3 5 4 1

Note:

本题由旧版NOJ导入,来源:kojimai

Info

NOJ

Provider NOJ

Code NOJ2074

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet