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
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
Output Specification
For each test case, you must correctly output on the first line
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 |
---|---|---|---|
Copy
|
Copy
|
Copy
|
Copy
|
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
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