Graph Relabeling

Time limit2sMemory limit128 MB

Summary

Given a directed graph as an adjacency matrix, assign each vertex a distinct label from 1 to N respecting all edge order constraints, and output the lexicographically smallest label sequence or -1 if impossible.

Level: Medium6 of 10
Topics: Topological sort, Greedy, Heap, Graph
Solved: No attempts yet

Problem

You are given a directed graph with N vertices. Assign each vertex i a distinct new number M_i from 1 through N.

For every directed edge from vertex u to vertex v, the numbering must satisfy M_u < M_v.

After assigning numbers, the result is the sequence M_1, M_2, ..., M_N. Output the lexicographically smallest sequence among all valid numberings.

Input

The first line contains the number of vertices N.

Each of the next N lines contains an adjacency matrix row. A 0 means there is no edge, and a 1 means there is a directed edge from the row vertex to the column vertex.

N is a positive integer no greater than 50.

Output

Print the sequence elements in order on one line, separated by spaces.

If no valid numbering exists, print -1. If multiple valid numberings exist, print the lexicographically smallest one.

Examples4

Example 1

Input

Expected output

1 2 5 3 4

Example 2
Input
```
3
010
001
100
```
Expected output
```
-1
```
Example 3
Input
```
4
0100
0010
0001
0000
```
Expected output
```
1 2 3 4
```
Example 4
Input
```
1
0
```
Expected output
```
1
```