Euler Circuit

Time limit3sMemory limit512 MB

Summary
Given an adjacency matrix with possible multi-edges, output a valid Euler circuit or -1 if none exists.
Level

Medium6 of 10

Topics
Graph, DFS, Implementation
Solved
No attempts yet

Problem

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.

Input

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

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

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

Output

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.

Examples1

  1. Example 1

    Input
    6
0 1 0 1 1 1
1 0 1 1 1 0
0 1 0 1 0 0
1 1 1 0 1 0
1 1 0 1 0 1
1 0 0 0 1 0
    Expected output
    1 2 3 4 1 5 2 4 5 6 1