Hoci sa každý z $n$ študentov počas celého semestra zodpovedne pripravoval na písomku z predmetu Počítačové siete, teraz to tak nevyzerá. Písomka pozostáva z 20 otázok a iba na jednu z nich je niekomu známa správna odpoveď. Presnejšie, $k$ študentov pozná správnu odpoveď na štvrtú otázku z písomky.
Medzi niektorými dvojicami študentov existujú obojsmerné komunikačné kanály (napríklad si posielajú SMSky [wow, to musí byť naozaj starý text úlohy...]), ktorými sa dajú šíriť správne odpovede. Dokonca platí, že každí dvaja študenti si môžu vymieňať informácie, či už priamym spojením alebo sprostredkovane cez iných.
V takomto stave má každý študent prístup k správnej odpovedi. Ale čo ak si skúšajúci donesie rušičku Wi-Fi, jastraba na chytanie poštových holubov, psa na detekciu vysokofrekvenčných signálov alebo iným spôsobom znemožní komunikáciu cez niektorý z kanálov?
Napíšte program, ktorý nájde všetky kritické komunikačné kanály. Kritický kanál je taký, že po jeho zničení sa aspoň jeden zo študentov nebude môcť dostať k správnej odpovedi na štvrtú otázku.
Prvý riadok vstupu obsahuje tri čísla: $n$, $m$, $k$. $n$ ($1 \leq n \leq 10^5$) je počet študentov, $m$ ($1 \leq m \leq 10^6$) počet komunikačných kanálov a $k$ ($1 \leq k \leq n$) počet študentov poznajúcich správnu odpoveď na štvrtú otázku.
Študenti sú očíslovaní od 1 do $n$. Druhý riadok obsahuje $k$ čísel: zoznam študentov, ktorí poznajú odpoveď na štvrtú otázku. Každý z nasledujúcich $m$ riadkov obsahuje dve čísla $p_i$ $q_i$ ($1 \leq p_i, q_i \leq n, p_i \neq q_i$) opisujúce dvojicu študentov, ktorých spája $i$-ty komunikačný kanál. Žiadna dvojica sa na vstupe nezopakuje.
Na prvý riadok vypíšte číslo $s$ — počet kritických komunikačných kanálov. Nasledujúcich $s$ riadkov má obsahovať ich popisy, dvojice čísel študentov $p$ $q$, ktorých kanál spája ($p < q$). Dvojice vypisujte v utriedenom poradí, teda najprv tie s menším $p$, v prípade rovnosti najprv tie s menším $q$.
6 6 2
4 5
1 4
3 2
1 3
2 1
3 5
6 5
1
5 6
Ak odstránime hrany $(1,4)$ alebo $(3,5)$, stále sa bude vedieť každý študent dozvedieť odpoveď na otázku číslo štyri.
5 4 1
1
1 3
3 2
4 5
2 4
4
1 3
2 3
2 4
4 5