시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1600 376 244 21.650%

문제

어느 점에서 출발하여 그래프 상에 있는 모든 간선을 지나되 한번 지난 간선은 다시 지나지 않고 출발점으로 돌아오는 회로를 오일러 회로라 한다. 단, 그래프는 양방향 그래프가 주어진다.

문제는 그래프가 주어졌을 때 오일러 회로 경로를 출력하는 것이다..
 

입력

첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 개 있을 수 있다. 인접행렬의 값은 0보다 크거나 같고, 10보다 작거나 같은 정수이다.

출력

첫 줄에 방문하는 점 순서를 공백으로 구분하여 출력한다. 단, 시작점은 어느 위치에서든 상관없고 아무 경로만 하나 찍으면 된다. 불가능한 경우에는 -1을 출력한다.
 

예제 입력

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

예제 출력

1 2 3 4 1 5 2 4 5 6 1

힌트

출처

  • 문제를 번역한 사람: author6