정점이 개인 방향 그래프가 있다. 정점은 로 번호가 매겨져 있다.
각 정점 에는 값 가 주어진다. 방향 간선은 다음 규칙에 따라 존재한다.
이 그래프에서 모든 정점을 정확히 한 번씩 방문하는 경로인 해밀턴 경로를 하나 찾아라.
경로에서 연속해서 방문하는 두 정점 사이에는 이동 방향과 같은 방향의 간선이 있어야 한다. 시작점으로 돌아올 필요는 없다.
예를 들어, , 이면 는 해밀턴 경로이다. 각 정점을 정확히 한 번씩 방문하고, , , 인 방향 간선이 모두 존재하기 때문이다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 해밀턴 경로가 존재하지 않으면 한 줄에 -1을 출력한다.
해밀턴 경로가 존재하면 경로가 방문하는 정점을 시작점부터 끝점까지 라 할 때, 한 줄에 를 공백으로 구분하여 출력한다. 는 의 순열이어야 하며, 모든 에 대해 정점 에서 정점 로 가는 방향 간선이 존재해야 한다.
첫 번째 테스트 케이스에서 인 경로가 해밀턴 경로이다.
두 번째 테스트 케이스에서는 해밀턴 경로가 존재하지 않는다.
나머지 출력도 각 테스트 케이스에서 주어진 조건을 만족하는 해밀턴 경로의 예시이다.
각 케이스는 다음과 같은 형식으로 주어진다.
가능한 답이 여러 가지라면 아무거나 출력해도 된다.
| 3 | 22 | (). 즉, 들이 나온 뒤 들이 나온다. 모든 원소가 이거나 모두 인 경우도 포함한다. |
| 4 | 47 | 추가적인 제약이 없다. |
