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$.