CYCLERUN - Riding in cycles

no tags 

There are N cities, numbered from 1 to N, in the country you are living. Each pair of the cities is connected with exactly one road. However, each road is a one-way road, so it is either possible to go directly from A to B or from B to A for each pair of cities (A, B).

You are living in city #1 and you are practicing for upcoming cycling marathon, so you want to construct the following training plan:

First day you have to ride over 3 roads starting from and finishing in city #1.

Second day you have to ride over 4 roads in the same manner.

Third day you have to ride over 5 roads.


The last, (N-2)-th, day you have to ride over N roads starting from and finishing in city #1.

You don't like to visit the same city more than once per day, so you have to find a training route for each day that passes through each city at most once. City #1 should appear only at the start and at the end of each route.

Write the program that, given the layout of the network, outputs training route for each day, or writes "impossible" if such training plan is not achievable.


The first line of input contains the integer N (3 ≤ N ≤ 1000), number of cities.

Each of the next N lines contains exactly N characters that describes network layout. j-th character in i-th of these lines is '1' if it is possible to ride from city number i to city number j, or '0' otherwise.


You should output training route for each day in a separate line. Training route consists of space separated integers - numbers of the cities in order they should be visited. Each training route starts and ends with 1.

If there is no achievable training plan, output word 'impossible' in a single line, instead.



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

hide comments
atatomir: 2017-01-27 17:36:29

If the answer is 'impossible', you must print '\n' as well.

Tony Beta Lambda: 2010-01-08 15:51:40

Be careful with extra whitespaces in the input data.

Added by:Luka Kalinovcic
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:own problem