PEG Judge - NOI '06 - The Clever Tour Guide

National Olympiad in Informatics, China, 2006

Day 2, Problem 2 - The Clever Tour Guide

Alex has recently fallen in love with the job of being a tour guide. Day and night, he thinks about taking tourists to see attractions at various places. It just so happens that city M is currently hosting the NOI, where lots of people are coming to visit. To help him, many of Alex's friends have recommended him to tourists requiring a tour guide.

City M contains n attractions, where Alex has already numbered from 1 to n. Between some attractions, there are bidirectional roads. Alex can tell the tourists to meet up at any attraction point, and then take them all sightseeing. In the end, he can also pick any attraction point to end the tour. However, none of the tourists would like to go to attractions that they've already visited on the tour. So, Alex cannot bring tourists to the same attraction more than once.

Alex wishes for you to help him design a plausible route, such that the tourists can visit as many attractions as possible.

Input Format

There are 10 test cases guide1.in ~ guide10.in that will be given to your program (through standard input). They can be downloaded here for you to study: guide.zip

The first line of input will be an integer T (1 ≤ T ≤ 10), the test case number. The second line will contain two integers n and m, respectively representing the number of attractions and the number of roads. The following m lines each contain two integers a and b, indicating that there is a bidirectional road between attraction a and attraction b.

Output Format

For each test case, you must correctly output on the first line p, indicating that the route you found passes through p attraction points. After that, p integers should follow, one per line, specifying the attraction points your route visits, in the order that they are visited.

Sample Input

Sample Output

Explanation

There are many answers, 4 of which are listed below. You may output any one of them.

Answer 1	Answer 2	Answer 3	Answer 4
4 1 2 4 5	4 1 2 5 4	4 3 2 4 5	4 3 2 5 4

Scoring

Your given score will be based on the difference between your answer and the correct answer. Assuming your answer is valid and the number of attractions you visit is x, also letting the result we've found to be ans, then your score out of 10 for the test case will be calculated as follows:

Score	Condition	Score	Condition
12	`x` > `ans`	5	`x` ≥ `ans`*0.93
10	`x` = `ans`	4	`x` ≥ `ans`*0.9
9	`x` ≥ `ans` − 1	3	`x` ≥ `ans`*0.8
8	`x` ≥ `ans` − 2	2	`x` ≥ `ans`*0.7
7	`x` ≥ `ans` − 3	1	`x` ≥ `ans`*0.5
6	`x` ≥ `ans`*0.95	0	`x` < `ans`*0.5