책 리뷰어

서평가는 책 $N$권을 서평해야 합니다. 각 서평은 책에 $1$부터 $M$까지의 척도로 점수를 매기면서 끝납니다. 각 책에 절대 점수를 바로 고르기는 어려우므로, 서평가는 책을 두 권씩 비교해서 어느 쪽이 더 나은지 적는 편이 훨씬 쉽다고 생각합니다.

서평가는 책에 $1$부터 $N$까지의 정수로 번호를 붙였고, 각 책의 점수 $a_1, a_2, \dots, a_N$을 정하려 합니다. 이를 위해 일부 책 쌍 $i, j$에 대해 $a_i$와 $a_j$의 관계를 설명하는 비교를 $R$번 했습니다.

서평가는 비교에서 나온 모든 조건을 만족하는 점수 배정이라면 어떤 것이든 받아들입니다. 그런 배정을 찾는 것을 도와주세요.

첫 줄에는 책의 수 $N$($1 \leq N \leq 100000$), 가능한 최고 점수 $M$($1 \leq M \leq 100000$), 비교 횟수 $R$($1 \leq R \leq 500000$)이 주어집니다.

이어서 반드시 성립해야 하는 관계를 나타내는 $R$개의 줄이 나옵니다. 각 줄은 <i> <relation> <j> 형식이며, $a_i$ <relation> $a_j$가 성립해야 한다는 뜻입니다. $i$와 $j$는 $1$부터 $N$까지의 정수이고, $i \neq j$입니다. relation은 <, =, ≤ 중 하나입니다. 같은 책 쌍은 두 번 이상 비교되지 않습니다.

모든 관계가 성립하고, 모든 수가 $[1, M]$ 범위에 있는 정수 목록 $a_1, a_2, \ldots, a_N$을 출력하세요. 답이 여러 개이면 그중 아무거나 출력해도 됩니다. 불가능하면 $-1$을 출력하세요.

첫 번째 입력 예제에서 1 2 1 3 3이 유효한 답입니다. 모든 수가 $[1, 3]$ 범위에 있고, 네 관계 $a_1 < a_2$, $a_2 < a_4$, $a_3 < a_2$, $a_2 < a_5$를 만족하는지 확인하면 됩니다.