Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: sequence.in

Rezultatų failas: sequence.out

Jei norite pateikti savo sprendimą - prisijunkite.

Seka

Petriukas žaidė su skaičių seka, kurioje buvo n skirtingų skaičių. Jis mėgdavo skaičius išdėstyti mažėjimo arba didėjimo tvarka. Tai pastebėjęs Petriuko brolis Antanukas, užsimanė Petriuką išmokyti sudėtingesnių dalykų ir sugalvojo uždengti skaičius lapeliais, ant kurių buvo surašytos raidės a_1, a_2, ..., a_n. Kiekviena raidė žymėjo kintamąjį.

Antanukas taip pat pasakė, kurie kintamieji didesni ar mažesni už kitus kintamuosius. Petriukas turi dvi užduotis:

  1. Surikiuoti kintamuosius taip, kad kiekvienas kintamasis iš jų, pagal Antanuko suteiktą informaciją, gali būti mažesnis už kiekvieną už jo einantį kintamąjį. Jei yra keli galimi variantai, reikia išrinkti leksikografiškai mažiausią seką pagal indeksų numerius. Pvz. jei viena seka yra a_1, a_3, a_2, o kita yra a_1, a_2, a_3, tai reikia atspausdinti antrąją, t.y. "1 2 3".
  2. Surikiuoti kintamuosius taip, kad kiekvienas kintamasis iš jų, pagal Antanuko suteiktą informaciją, gali būti didesnis už kiekvieną už jo einantį kintamąjį. Jei yra keli galimi variantai, reikia išrinkti leksikografiškai didžiausią seką pagal indeksų numerius. Pvz. jei viena seka yra a_1, a_3, a_2, o kita yra a_1, a_2, a_3, tai reikia atspausdinti pirmąją, t.y. "1 3 2".

Padėkite Petriukui atlikti užduotis! Gali būti, kad Antanukas Petriuką apgavo arba tiesiog padarė klaidą. Į šį variantą irgi reikėtų atsižvelgti.

Įvestis

Pirmoje eilutėje atskirti tarpu pateikti du sveikieji skaičiai n ir m (1\\leqn\\leq10^5, 0\\leqm\\leq10^5). Kitose m eilučių yra pateikta "i < j" (reiškia a_i<a_j) arba "i > j" (reiškia a_i>a_j

Išvestis

Atspausdinkite dvi eilutes.

Pirmoje eilutėje turi būti indeksai, atskirti tarpu, atitinkantys atsakymą į pirmąją užduotį.

Antroje eilutėje turi būti indeksai, atskirti tarpu, atitinkantys atsakymą į antrąją užduotį.

Jei užduočių padaryti neįmanoma, reikia išspausdinti ":(" (kabutės tik dėl aiškumo).

Pavyzdžiai

Duomenys Rezultatai 
2 1
1 < 2
 
1 2
2 1
 
2 1
1 > 2
 
2 1
1 2
 
2 2
1 > 2
1 < 2
 
:(