Euler Circuit

You are given an undirected graph. An Euler circuit is a route that starts at some vertex, uses every edge of the graph exactly once, and returns to the starting vertex.

Find and print one Euler circuit in the given graph.

The first line contains the number of vertices $N$. ($1 \le N \le 1{,}000$)

Each of the next $N$ lines contains one row of the adjacency matrix. The $i$-th of these rows describes the number of edges between vertex $i$ and every other vertex. Each matrix value is an integer from $0$ to $10$, and multiple edges may exist between the same two vertices.

The input graph has no self-loops, and the graph is connected.

If an Euler circuit exists, print the visited vertex numbers in order on one line, separated by spaces. The starting vertex may be any vertex, and any valid circuit is accepted.

If no Euler circuit exists, print -1.