2222번 - 아이스크림 스페셜 저지

인간의 선호도에서 "A를 B보다 더 좋아하고, B를 C보다 더 좋아하면 A를 C보다 더 좋아 한다"는 명제가 성립할 때 전이 선호도가 성립한다고 한다. 어떤 두 가지를 비슷하게 좋아하는 경우도 마찬가지로 전이 선호도가 성립할 수 있다. 예를 들어, A와 B를 비슷하게 좋아하고, B를 C보다 더 좋아하면, A를 C보다 더 좋아하는 전이 선호도 관계가 성립한다.

만약, 전이 선호도 관계가 성립하면 n개의 아이스크림이 주어졌을 때, 전이 선호도에 따라 아이스크림을 배열할 수 있다. I₁, I₂, ..., I_n의 아이스크림 배열에 대해, i < j인 모든 i, j에 대해 I_i를 I_j보다 더 좋아하거나 비슷하게 좋아하는 관계가 성립하게 말이다. 예를 들어, 철수가 여러 가지 아이스크림 종류 중 초콜릿을 딸기보다 좋아하고, 딸기를 호두보다 좋아하고, 호두와 바닐라는 비슷하게 좋아한다고 한다. 철수의 전이 선호도에 따라 아이스크림을 배열하면 "초콜릿, 딸기, 호두, 바닐라" 또는 "초콜릿, 딸기, 바닐라, 호두" 가 된다.

하지만 인간의 선호도는 가끔 복잡할 때가 있다. 철수는 분명히 초콜릿을 호두보다 좋아하지만, 초콜릿과 호두 두개를 비교하면 호두를 초콜릿보다 더 좋아한다고 하는 것이다. 이와 같은 경우에는 전이 선호도가 성립하지 않기 때문에 전이 선호도에 따라 정렬할 수 없다. 따라서 일관성 선호도라는 것을 이용한다.

I₁, I₂, ..., I_n의 아이스크림 배열에 대해 모든 i = 1, 2, ..., n-1에 대해 I_i를 I_i+1보다 더 좋아하거나 비슷하게 좋아하는 관계가 성립하면 일관성 선호도에 따라 정렬되었다고 한다. 즉, 위의 예제에서 호두를 초콜릿보다 더 좋아한다는 사실을 추가한 경우, "초콜릿, 호두, 딸기, 바닐라"는 일관성 선호도에 따라 정렬되지 않았지만, "초콜릿, 딸기, 호두, 바닐라"는 일관성 선호도에 따라 정렬되었다고 할 수 있다.

n개의 아이스크림 1, 2, ..., n이 주어지고, 임의의 두 개의 아이스크림 사이에 어떤 아이스크림을 더 좋아하는지, 또는 비슷하게 좋아하는지가 주어질 때, 일관성 선호도에 따라 아이스크림을 배열하는 프로그램을 작성하시오.

첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어지고, 둘째 줄부터 n개의 줄에 각 줄에 n개의 문자가 주어진다. 둘째 줄부터 i번째 줄의 j번째 문자 g_i,j가 '+'이면 아이스크림 i를 아이스크림 j보다 더 좋아하고, '-'이면 아이스크림 j를 아이스크림 i보다 더 좋아하고, '0'이면 비슷하게 좋아하는 것을 나타낸다. i번째 줄의 i번째 문자는 'x'로 주어진다. i와 j가 같지 않은 경우에 g_i,j가 '+'이면 g_j,i는 '-', g_i,j가 '-'이면 g_j,i는 '+', g_i,j가 '0'이면 g_j,i는 '0'이다. 

첫째 줄에 일관성 선호도에 따라 정렬된 아이스크림 배열을 출력한다. 해가 여러 개 존재하는 경우에는 그 중 하나를 출력한다. 일관성 선호도에 따라 정렬할 수 없는 경우에는 첫째 줄에 -1만을 출력한다.