People's preferences are seldom rational. For example, little Johnny's. Johnny likes ice cream a lot. One of his favorite ice creams is Chocolate. He likes it even more than Strawberry. He also likes Strawberry more than Hazelnut, and he is not completely sure whether Hazelnut is better than Vanilla or vice versa; he likes them about the same. But interestingly, if he had to choose only between Chocolate and Hazelnut, he would choose Hazelnut. By further introspection, Johnny also found that he prefers Chocolate to Vanilla, and Vanilla to Strawberry ice cream.
Does this sound messy and confusing? Yes? Ok, your job will be to make some sense out of it. Usually we assume that people's preferences over a set of items are transitive, i.e. if they prefer A to B and B to C, they also prefer A to C. Similarly, if they are indifferent between A and B and prefer B to C (C to B), then they also prefer A to C (C to A). And if they are indifferent between A and B and also between B and C, they are also indifferent between A and C.
With transitive preferences, one can order all items in question into a sequence I1, I2,..., In, so that for all i<j, item Ii is preferred to item Ij, or the person is indifferent between Ii and Ij.
If the preferences are not transitive, as in Johnny's case (e.g. he prefers Strawberry to Hazelnut and is indifferent between Hazelnut and Vanilla, but prefers Vanilla to Strawberry), one can still try to order the items into a sequence I1, I2,..., In, so that for every i=1,...,N-1, item Ii is preferred to item Ii+1, or these two items are indifferent. Such an ordering is called consistent with the preferences.
Given Johnny's preferences between various ice cream flavors, your task is to find an ordering of the flavors that is consistent with his preferences.
The first line of the input file contains a single number N - the number of flavors of ice cream. Next N lines contain N characters each. The j-th character in the i-th row describes Johnny's preference between flavors i and j. For i=j, this character will always be X. If Johnny prefers flavor i to flavor j, this character will be *. If he prefers flavor j to flavor i, this character will be ., and if he is indifferent between i and j, this character will be 0. You can assume that if Johnny prefers i to j, he doesn't prefer j to i, and if he is indifferent between i and j, he is also indifferent between j and i.
The output file should contain N numbers, separated by spaces or end-of-line characters. These numbers specify one possible ordering of the ice cream flavors consistent with Johnny's preferences. If no such ordering exists, the output file should contain a single word "impossible".
4 X*.* .X*. *.X0 .*0XOutput file: (one out of more possible)
1 2 3 4
Note: Another possibility is 4 3 1 2