스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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, …, 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 ≤ N ≤ 10^5), M (1 ≤ M ≤ 10^5), R (1 ≤ R ≤ 5 · 10^5), 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 ≠ 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, …, 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.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
| Grupp | Poängvärde | Gränser |
| 1 | 30 | R kan bara vara < |
| 2 | 30 | R kan bara vara < eller = |
| 3 | 40 | Inga ytterligare begränsningar |
Förklaring av exempelfall 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.
예제
예제 1
5 3 4 1 < 2 2 < 4 3 < 2 2 < 5
1 2 1 3 3
예제 2
3 10 3 1 < 2 2 < 3 3 < 1
-1
예제 3
6 4 6 2 < 1 3 = 1 6 = 3 6 < 5 5 < 4 1 < 4
2 1 2 4 3 2
예제 4
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