National Olympiad in Informatics, China, 2006
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 attractions, which Alex has already numbered from
to
. 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 Specification
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
, the
test case number. The second line will contain two integers
and
,
respectively representing the number of attractions and the number of
roads. The following
lines each contain two integers
and
,
indicating that there is a bidirectional road between attraction
and
attraction
.
Output Specification
For each test case, you must correctly output on the first line ,
indicating that the route you found passes through
attraction
points. After that,
integers should follow, one per line, specifying
the attraction points your route visits, in the order that they are
visited.
Sample Input
0
5 5
1 2
3 2
2 4
2 5
4 5
Sample Output
4
1
2
4
5
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 |
---|---|---|---|
|
|
|
|
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 , also letting the result we've found to be
, then your score out of 10 for the test case will be calculated as
follows:
Score | Condition | Score | Condition |
---|---|---|---|
12 | 5 | ||
10 | 4 | ||
9 | 3 | ||
8 | 2 | ||
7 | 1 | ||
6 | 0 |
If there are multiple conditions satisfied, then the maximum score of the conditions is taken.
Problem translated to English by .
Comments