Kići i Ćiki su već dugo najbolji drugari. Nažalost, Kići je izgubio pamćenje i Ćiki je odlučio da mu spremi specijalno iznenađenje kako bi mu pomogao da se seti svega. On je sve njihove zajedničke uspomene zapisivao u jednu zelenu sveskicu, i sada on želi da od toga napravi jednu od onih knjižica gde je čitaocu povremeno ponuđeno da izabere kako će se priča nastaviti. Na kraju svakog dela priče, čitalac bira da li će nastaviti onako kako bi Kići nastavio ili onako kako bi Ćiki nastavio, s tim što se sa nekih delova ne može nastaviti dalje (na njima se priča završava), a na pojedinim delovima postoji samo jedna mogućnost da se nastavi priča (nekad je to Ćikijeva a nekad Kićijeva ideja). U toku jednog čitanja ne možemo dva puta da se nađemo na istom delu i do svakog dela priče se može stići na jedinstven način. Svaki deo priče se nalazi na po jednoj stranici.

Delovi ove priče su numerisani brojevima od 1 do n (gde je n broj delova priče) ali pošto je Ćiki perfekcionista on želi da ih renumeriše (opet brojevima od 1 do n). Ćiki je uvek voleo male stvari, a Kići velike, pa zato Ćiki želi da: ako sa dela priče koji je na stranici a prelazimo na deo priče koji je na stranici b važi:

• Ako smo izabrali ono što bi Kići uradio, onda je b > a, i redni broj svake stranice do koje ćemo kasnije u toku čitanja priče moći da dođemo je veći od a

• Ako smo izabrali ono što bi Ćiki uradio, onda je b < a, i redni broj svake stranice do koje ćemo kasnije u toku čitanja priče moći da dođemo je manji od a

  Pomozite Ćikiju da složi stranice kako bi što pre mogao da da knjižicu Kićiju (Ćiki je sjajan programer, ali je trenutno previše tužan da bi razmišljao o ovom problemu).

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu nalaze se tri broja n, k i c(1 ≤ n ≤ 250.000, 1 ≤ k, c ≤n). Zatim se u narednih k redova nalaze po dva broja, a ib, koji označavaju da sa dela priče obeleženog brojema ako poslušamo Kićija prelazimo na deo obeleženbrojem b. Slično se u narednih c redova nalaze po dvabroja, a i b, koji označavaju da sa dela pričeobeleženog brojem a ako poslušamo Ćikija prelazimo nadeo obeležen brojem b. Pre renumerisanja početak pričeje na delu obeleženom brojem 1 (obratite pažnju da poslerenumeracije ne mora biti).

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) Treba da se sastoji od n redova - u i-tomredu nalazi se broj stranice na kojoj će se deo pričeobeležen brojem i nalaziti posle renumeracije. Ako postojiviše rešenja, štampati bilo koje.

Primer 1.

7 3 3
3 6
1 3
5 7
1 2
3 5
2 4

3
2
6
1
4
7
5