Mexico

Official version
IOI’06

English

Version 1.1

Number of pages 1
IOI’06
Page 1
THE VALLEY OF MEXICO

Mexico City is built in a beautiful valley known as the Valley of Mexico which, years ago, was mostly
a lake. Around the year 1300, Aztec religious leaders decreed that the lake’s center be filled in
order to build the capital of their empire. Today, the lake is completely covered.

Before the Aztecs arrived, c cities were located around the lake on its shores. Some of these cities
established commercial agreements. Goods were traded, using boats, between cities that had a
commercial agreement. It was possible to connect any two cities by a line segment through the
lake.

Eventually, the kings of the cities decided to organize this commerce. They designed a commerce
route that connected every city around the lake. The route met the following requirements:
•
It could start in any of the cities, visited each of the cities around the lake, and finally ended
in another city different from the starting city.
•
The route visited each city exactly once.
•
Every pair of consecutively visited cities in the route had a commercial agreement.
•
Every pair of consecutively visited cities in the route was connected by a line segment.
•
To avoid crashes between boats, the route never crossed itself.

The figure shows the lake and the cities around it. The
lines (both thick and thin) represent commercial
agreements between cities. The thick lines represent a
commerce route starting in city 2 and ending in city 5.

This route never crosses itself. It would not be legal, for
example, to construct a route that went from 2 to 6 to 5 to
1, since the route would cross itself.

Cities in the lake are numbered from 1 through c moving
in clockwise direction.

TASK
Write a program that, given both the count c of cities and a list of the commercial agreements
between them, constructs a commerce route that meets the above requirements.

Note (RiseOJ) — The original statement describes file-based input/output; on this judge your program must read from standard input and write to standard output instead.

3 ≤ c ≤ 1000

Number of cities around the lake.

Mexico

Official version
IOI’06

English

Version 1.1

Number of pages 2
IOI’06
Page 2

Your program must read the following data from the file mexico.in
mexico.in
DESCRIPTION
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7
LINE 1: Contains integer c
LINE 2: Contains an integer n that represents the number of
commercial agreements
NEXT n LINES: Each line represents a unique commercial
agreement. Every line contains two space-separated integers
that represent the two cities involved in the agreement.

Your program must output the following data to the file mexico.out
mexico.out
DESCRIPTION
2
3
4
1
7
6
5
If it’s possible to construct the commerce route, write c lines, each
with an integer that represents the order in which the cities are visited
in the commerce route. If it’s not possible to construct a commerce
route that meets all the requirements, output a single line containing
the number -1.

NOTE: If there is more than one commerce route that meets the requirements, any of them you
output will be considered correct.

GRADING
For a set of test cases worth a total of 40 points, each test case will meet the following
requirements:

3 ≤ c ≤ 20

생성자가 기록되지 않았습니다.

출처 IOI 2006