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

Ulaz.

(Ulazni podaci se nalaze u datoteci knjizica.in) 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 i b, koji označavaju da sa dela priče obeleženog brojem a ako poslušamo Kićija prelazimo na deo obeležen brojem b. Slično se u narednih c redova nalaze po dva broja, a i b, koji označavaju da sa dela priče obeleženog brojem a ako poslušamo Ćikija prelazimo na deo obeležen brojem b. Pre renumerisanja početak priče je na delu obeleženom brojem 1 (obratite pažnju da posle renumeracije ne mora biti).

Izlaz.

(Izlazne podatke upisati u datoteku knjizica.out) Treba da se sastoji od n redova - u i-tom redu nalazi se broj stranice na kojoj će se deo priče obeležen brojem i nalaziti posle renumeracije. Ako postoji viš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

#include <stdio.h>
#include <stdlib.h>

const int maxN = 500000;

int levi[maxN + 1];
int desni[maxN + 1];
int strana[maxN + 1];
int brojac;

void numerisi(int deo) {
     if (deo == -1) return;
     numerisi(levi[deo]);
     brojac++;
     strana[deo] = brojac;
     numerisi(desni[deo]);    
}

int main(){   
    int n, k, c, a, b;
    
    freopen("knjizica.in", "r", stdin);
    scanf("%d %d %d",&n, &k, &c);
    for (int i = 1; i <= n; i++) {
        levi[i] = -1; 
        desni[i] = -1;
    }
    for (int i = 1; i <= k; i++) {
        scanf("%d %d", &a, &b);
        desni[a] = b;
    }
    for (int i = 1; i <= c; i++) {
        scanf("%d %d", &a, &b);
        levi[a] = b;
    }
    
    brojac = 0;
    numerisi(1);
    
    freopen("knjizica.out", "w", stdout);
    for (int i = 1; i <= n; i++)
        printf("%d\n", strana[i]);    
        
    return 0;
}