26919번 - Bokrecesioner 스페셜 저지다국어

문제

En bokrecensent har läst $N$ böcker som ska recenseras. Varje recension ska avslutas med att boken tilldelas ett betyg på en skala från 1ドル$ till $M$. Det kan vara svårt att direkt välja ett absolut betyg för varje bok, så bokrecensenten tycker att det är mycket enklare att jämföra två böcker i taget med varandra och beskriva vilken av dem som är bäst.

Bokrecensenten har numrerat böcker med heltal från 1ドル$ till $N$ och vill nu bestämma deras betyg $a_1, a_2, \dots , a_N$. För att göra det har bokrecensenten gjort $R$ jämförelser som beskriver relationen mellan $a_i$ och $a_j,ドル för några böcker $i, j$.

Bokrecensenten är nöjd med vilken betygsättning som helst, så länge alla krav från jämförelserna är uppfyllda. Hjälp bokrecensenten att hitta en sådan betygsättning.

입력

Första raden består av tre heltal, $N$ (1ドル \leq N \leq 100,000円$), $M$ (1ドル \leq M \leq 100,000円$), $R$ (1ドル \leq R \leq 500,000円$) -- antalet böcker, högsta möjliga betyget och antalet jämförelser.

Sedan följer $R$ rader med relationer som ska vara uppfyllda. Varje sådan rad har formatet "<i> <relation> <j>", som beskriver relationen mellan $a_i$ och $a_j$. $i$ och $j$ är heltal mellan 1ドル$ och $N,ドル $i \neq j$. Relationen $r$ är någon av strängarna '<', '=', '≤', och detta beskriver just att $a_i$ <relation> $a_j$ måste gälla. Inget par av böcker kommer att jämföras mer än en gång.

출력

Skriv ut en lista med heltal $a_1, a_2, \ldots , a_N$ sådan att alla relationer håller, och alla tal är på intervallet $[1, M]$. Om det finns flera lösningar, skriv ut vilken som helst. Om det är omöjligt, skriv ut $-1$.

제한

힌트

I det första indataexemplet så är 1 2 1 3 3 en giltig lösning. Detta kan verifieras genom att se att alla tal ligger på intervallet $[1, 3],ドル och att talen uppfyller de fyra relationerna $a_1 < a_2,ドル $a_2 < a_4,ドル $a_3 < a_2$ och $a_2 < a_5$.