아이스크림

어떤 사람이 여러 아이스크림에 대해 선호 관계를 말한다. 두 아이스크림 A와 B에 대해 A를 B보다 더 좋아하거나, 둘을 비슷하게 좋아하거나, B를 A보다 더 좋아한다는 정보가 주어진다.

선호 관계가 항상 전이적이라면 모든 아이스크림을 한 줄로 배열하여, 앞에 있는 아이스크림이 뒤에 있는 모든 아이스크림보다 더 좋거나 비슷하게 좋다고 말할 수 있다. 하지만 실제 선호는 전이적이지 않을 수 있으므로, 여기서는 더 약한 조건인 일관성 선호도를 사용한다.

아이스크림 배열 I1, I2, ..., In이 있을 때, 모든 i = 1, 2, ..., n - 1에 대해 Ii를 Ii+1보다 더 좋아하거나 비슷하게 좋아하면 이 배열은 일관성 선호도에 따라 정렬되었다고 한다.

n개의 아이스크림 1, 2, ..., n과 모든 두 아이스크림 사이의 선호 관계가 주어진다. 일관성 선호도에 따라 정렬된 아이스크림 배열을 구하시오.

첫째 줄에 정수 n(1 <= n <= 1,000)이 주어진다.

다음 n개의 줄에는 각각 n개의 문자가 주어진다. 이 중 i번째 줄의 j번째 문자 gi,j는 아이스크림 i와 아이스크림 j의 관계를 나타낸다.

• gi,j가 '+'이면 아이스크림 i를 아이스크림 j보다 더 좋아한다.
• gi,j가 '-'이면 아이스크림 j를 아이스크림 i보다 더 좋아한다.
• gi,j가 '0'이면 두 아이스크림을 비슷하게 좋아한다.

항상 gi,i는 'x'이다. i와 j가 다르면 gi,j와 gj,i는 서로 모순되지 않게 주어진다. 즉, 한쪽이 '+'이면 다른 쪽은 '-'이고, 한쪽이 '0'이면 다른 쪽도 '0'이다.

첫째 줄에 일관성 선호도에 따라 정렬된 아이스크림 번호의 배열을 출력한다. 가능한 배열이 여러 개이면 그중 아무거나 출력해도 된다.

일관성 선호도에 따라 정렬할 수 없으면 첫째 줄에 -1만 출력한다.