Problem C. Cup and Championship

Author:I. Ludov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

The city of Kislodriftinsk holds two prestigious drifting contests with different rules.

The Kislodriftinsk Drifting Championship consists of head-to-head matches between all pairs of pilots. Judging rules exclude draws, so after every match exactly one participant receives one score point. The champion of Kislodriftinsk is determined as the pilot with maximum summary score (i. e. beating maximum number of other participants). Note that there may be several champions with equal scores.

The Kislodriftinsk Drifting Cup is conducted by olympic play-off system (aka single elimination). All participants are divided into pairs and winners of every pair are determined. Winners then make new pairs and the process is repeated until there is only one participant left, who becomes a cup winner.

Rising star of Kislodriftinsk motorsports, Kesha Tsuchiyev, has already became one of Championship winners this year and now wants to also win in the forthcoming Cup. His task is simplified by the fact that both contests have same set of participants and same judge teams. This implies that the result of every match in the Cup will be the same as in the Championship with the same pair of participants. Being one of Championship winners, Kesha will win a significant proportion of possible Cup matches.

However, Kesha suspects that in the case of unfortunate pair composition, he may not even advance to second stage, having lost the very first match. Your program must help him calculate any Cup schedule which leads him to victory, or determine that it is impossible.

Input file format

Input file contains integers N T. Following N lines contain N integers each — a matrix of head-to-head matches results. A number in row i and column j is equal 1 if i-th pilot wins against j-th and 0 otherwise. Diagonal contains zeroes. Kesha Tsuchiyev is a pilot number T, numbers start from zero.

Output file format

Output file must contain N integers s0,i which is a permutation of pilot numbers 0… N − 1 determining a schedule of play-off championship as follows: In the first round N / 2 matches are conducted between pairs (s0,0 vs s0,1), (s0,2 vs s0,3), etc. Winners of these matches form a sequence s1,i. Then the process is repeated, i.e. N / 4 matches are conducted between pairs (s1,0 vs s1,1), (s1,2 vs s1,3) etc. The winner of play-off cup is the only number left in the sequence sk,i for some k, and this number must be equal to T. If there is no solution, output file must contain a single integer  − 1.

Constraints

2 ≤ N ≤ 64, N is a power of 2, 0 ≤ T < N

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 2
0 1 0 0
0 0 0 0
1 1 0 1
1 1 0 0
1 2 0 3
2
4 2
0 1 0 0
0 0 1 0
1 0 0 1
1 1 0 0
2 3 0 1

0.073s 0.007s 13