Laiko ribojimas: 2s

Atminties ribojimas: 64MB

Duomenų failas: kritiniai.in

Rezultatų failas: kritiniai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kritiniai laidai

Kompiuterių tinkle yra N kompiuterių, sunumeruotų nuo 1 iki N. Kai kurias jų poras jungia M dvikryptės komunikacijos laidų. Yra žinoma, jog tinklas jungus, t. y. egzistuoja kelias tinkle tarp bet kurios kompiuterių poros. Kai kurie kompiuteriai visiems kompiuteriams (įskaitant save) teikia paslaugą A, kai kurie – paslaugą B. Tas pats kompiuteris gali teikti abi paslaugas. Kiekvienas kompiuteris privalo turėti prieigą prie abiejų paslaugų.

Gali nutikti, jog nutraukus kurį nors laidą kuri nors paslauga kuriam nors kompiuteriui taps nepasiekiama. Laidas, pasižymintis šia savybe, vadinamas kritiniu laidu. Raskite, kurie laidai yra kritiniai.

Pradiniai duomenys

Pirmoje eilutėje yra 4 sveikieji skaičiai – N, M, K ir L (1\\leqN\\leq100~000, 1\\leqM\\leq1~000~000, 1\\leqK,L\\leqN). Antroje eilutėje yra K tarpais atskirtų sveikųjų skaičių – numeriai kompiuterių, teikiančių paslaugą A. Trečioje eilutėje yra L tarpais atskirtų sveikųjų skaičių – numeriai kompiuterių, teikiančių paslaugą B. Tolesnėse M eilučių yra po du tarpu atskirtus sveikuosius skaičius A_i ir B_i – numerius kompiuterių, kuriuos jungia laidas (A_i\\neqB_i). Kiekvieną kompiuterių porą jungia ne daugiau negu vienas laidas.

Rezultatai

Pirmoje eilutėje išveskite kritinių laidų skaičių R. Tolesnėse R eilučių bet kokia tvarka išveskite po du tarpu atskirtus sveikuosius skaičius – numerius kompiuterių, kuriuos jungia kritinis laidas.

Pavyzdžiai

Pradiniai duomenys Rezultatai
9 10 4 3
3 8 9 4
4 2 5
1 2
6 7
9 7
2 3
4 1
5 6
7 8
6 8
4 2
1 5
3
5 6
9 7
2 3