III Olympiad in Informatics 1995/1996
|
Task: GON
|
Author: Krzysztof Diks
|
I stage contest |
King Informaticus, a ruler of Byteland has a lot to worry about. Secret service informed
him that a cruel King Hacker is about to attack his kingdom. Moreover, secret agents
of Hacker have been already sent to one of the cities in
Byteland in order to hinder preparations for defense. Informaticus decided to warn his subjects against an oncoming danger.
Citizens of Byteland live only in cities. Cities have numbers from 1 to n, where 3 <=
n <= 500. The capital city has
number 1. There is a well developed system of roads in Byteland, all of them are
two-way roads. Any two cities have no more than one
direct connection, but for any two different cities A and B one can get from
A to B and then return from B to A without going
again through any of the cities on the way from A to B.
King Informaticus decided to send two messengers to warn his subjects. Each
messenger moves on the roads of Byteland and may visit one city a couple of times. But the order in which they arrive to certain cities
for the first time should be in accord with King's plan.
The plan is a series of n integers x1, x2, ...,
xn from the interval [1..n], where
x1 = 1. On the way from the city xi to the city
xi+1 an agent can go through any finite number of cities, but only these that he had visited before. Unfortunately,
spies of King Hacker sat a trap to catch the messengers and imprison any of them who comes to the
occupied city. Thus the plan of routes of two messengers should be such that each
city is visited by at leas one messenger, before they will be captured by agents
hidden in one of the cities different than the capital.
Write a program that:
In this case the correct solution is the file GON.OUT:
1 2 3 5 4
1 4 5 3 2
The first messenger could move on the route : 1 2 3 2 5 4, and the second one on the route : 1 4 5 4 3 2.
Your program should look for the file GON.IN in the current directory and produce the output file GON.OUT in the current directory too. The file containing the source code of your program should have a name GON.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in file GON.EXE