Problem C
Bokrecensioner

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.

Indata

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.

Utdata

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.

Exempel

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 de fyra relationerna $a_1 < a_2$, $a_2 < a_4$, $a_3 < a_2$ och $a_2 < a_5$ är uppfyllda. Villkoren gäller fortfarande om vi stoppar in värdena på $a_ i$ från lösningen, alltså är lösningen giltig.

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

• För 30 poäng gäller att endast relationen < kan förekomma.

• För ytterligare 30 poäng gäller att endast relationerna < och = kan förekomma.

5 3 4
1 < 2
2 < 4
3 < 2
2 < 5

1 2 1 3 3

3 10 3
1 < 2
2 < 3
3 < 1

-1

6 4 6
2 < 1
3 = 1
6 = 3
6 < 5
5 < 4
1 < 4

2 1 2 4 3 2

7 3 8
1 <= 2
5 = 7
2 <= 7
6 < 1
5 <= 1
2 < 3
6 <= 4
4 = 3

2 2 3 3 2 1 2