12287번 - 해밀턴 경로 스페셜 저지

N개의 정점과 N(N-1)/2개의 간선으로 이루어진 방향 그래프 G가 있다. 정점은 0부터 N-1까지 번호가 매겨져 있다. 서로 다른 두 정점 (i, j) 사이에는 i에서 j로 가는 간선 또는 j에서 i로 가는 간선이 하나만 존재한다. 따라서, 간선의 방향을 무시하면 G는 완전 그래프이다.

X는 그래프 G의 인접 행렬을 의미한다. X_i,j가 '+'인 경우 i에서 j로 가는 간선이 있는 것이고, '-'인 경우 없는 것이다. X_i,i는 항상 '.' 이다.

G의 해밀턴 경로는 G의 모든 정점을 한 번씩 포함하는 길이가 N인 경로를 의미한다. 그래프의 G가 주어졌을 때, 해밀턴 경로를 찾아보자.

첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접 행렬 X가 주어진디. 여기서 i번째 줄의 j번째 문자는 X_i,j이다.

그래프 G의 해밀턴 경로가 존재하는 경우 해밀턴 경로에 포함되는정점을 순서대로 공백으로 구분해 출력한다. 존재하지 않는 경우 -1을 출력한다.

• 2 ≤ N ≤ 100