Zadanie

Ilavské problémy

Počet bodov: 55, časový limit: 1000ms

V Ilave stojí väzenie. A ako to už v takých väzeniach býva, bývajú v nich väzni. Bol by to na Ilavskom hrade¹ pokojný život, kebyže nie tých väzňov! Intrigujú, robia problémy, dohadujú sa, utekajú a iné nepríjemné záležitosti.

Nové vedenie väzenia sa rozhodlo, že s tým raz a navždy urobí poriadok. Zbúra niektoré chodby vo väzení, do styku so sebou príde menej väzňov a hneď bude po všetkých problémoch!

Lenže, ako sa to s problémami býva, ich riešenia nebývajú tak jednoduché, ako by sme chceli. A tak aj tuná prišiel riaditeľ na istý zádrheľ. Každý väzeň sa potrebuje totiž niekde sprchovať a niekde jesť. Niektoré bloky ciel obsahujú sprchy a niektoré iné jedálne.

Zistite, koľko najviac chodieb môže riaditeľ zbúrať, tak, aby každý väzeň mal k dispozícii ako jedlo, tak aj hygienu.

Vstup a výstup

Väzenie si môžeme predstaviť ako \(N\) blokov ciel, poprepájaných \(N - 1\) chodbami. Na začiatku sa z každého bloku dá dostať do každého. V niektorých \(J\) blokoch je jedáleň, v niektorých iných \(S\) blokoch sú sprchy.

Na vstupe dostanete v prvom riadku čísla \(N\), \(J\) a \(S\) oddelené medzerami.

Na ďalšom riadku dostanete \(J\) čísel oddelených medzerami – čísla blokov, v ktorých je jedáleň a na ďalšom riadku zas \(S\) čísel oddelených medzerami – čísla blokov, v ktorých je jedáleň.

Na posledných \(N - 1\) riadkoch sú medzerami oddelené čísla ciel \(a_i\) a \(b_i\), čísla blokov poprepájaných (obojsmernou) chodbou.

Na výstup vypíšte na prvom riadku číslo \(k\) - koľko najviac chodieb vieme zbúrať. Na ďalších \(k\) riadkoch vypíšte \(k\) chodieb – tie ktoré môžme zbúrať. Ak existuje viac riešení s optimálnym \(k\) vypíšte ľubovoľné.

Obmedzenia

\(2 \leq N \leq 100,000\) \(L + S \leq N\) \(L, S \geq 1\) \(0 \leq a_i, b_i < N\)

V \(30 \%\) vstupoch bude plati, že \(a_i = i\) a \(b_i = i + 1\), t.j. že väzenie bude čiara.

V \(40 \%\) vstupoch bude \(N \leq 1000\).

Príklad

Input:

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

Output:

1
0 2

Tu máme dve jedálne aj dve sprchy, vieme rozdeliť väzňov na najviac dve skupiny, pričom musíme zbúrať chodbu 0-2

Input:

6 3 3
2 0 1
3 4 5
0 1
1 2
0 3
0 4
4 5

Output:

0

Tu máme síce jedální aj spŕch síce veľa, rozdeliť väzňov ale nevieme.

Input:

8 4 2
1 5 2 7
3 6
0 1
1 2
2 3
3 4
4 5
5 6
6 7

Output:

1
5 4 

Rovnako správne by bolo aj zbúrať stenu 3-4.