CYCLERUN  Riding in cycles
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 oneway 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, (N2)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.
Input
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. jth character in ith of these lines is '1' if it is possible to ride from city number i to city number j, or '0' otherwise.
Output
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.
Example
Input: 5 01000 00011 11001 10100 10010 Output: 1 2 5 1 1 2 4 3 1 1 2 4 3 5 1
hide comments
atatomir:
20170127 17:36:29
If the answer is 'impossible', you must print '\n' as well. 

Tony Beta Lambda:
20100108 15:51:40
Be careful with extra whitespaces in the input data. 
Added by:  Luka Kalinovcic 
Date:  20090707 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  own problem 