Tagy: Python 2 queue
Obtiažnosť: hard

Párty

Po skončení súťažnej časti programu ACM ICPC sa súťažiaci tešia na veľká párty s jahodami a šampanským. Mnohí účastníci sú ale introvertní a aj keď chuť majú, na party sa hanbia ísť, ak sa na nej nezúčastní určitý počet kamarátov.

Na prvom riadku vstupu sú tri celé čísla: počet súťažiacich N(1N200,000)N \, (1 \leq N \leq 200, 000), počet dvojíc, kto sa s kým pozná M(0M600000)M \, (0 \leq M \leq 600\,000) a číslo K(0KN1)K\, (0 \leq K \leq N − 1). Súťažiacich pre jednoduchosť označíme číslami 11NN. Nasleduje MM riadkov, na každom sú dve čísla popisujúce dvojicu účastníkov, ktorí sa kamarátia. Môžete predpokladať, že tieto dve čísla sú z rozsahu 11NN, sú rôzne a tiež že na každom z týchto riadkov je rôzna dvojica čísel.

Každý z účastníkov je schopný ísť na párty len vtedy, ak sa na nej zúčastní aspoň KK jeho kamarátov. Niektoré podmnožiny účastníkov túto podmienku spĺňajú a niektoré nespĺňajú. Napríklad prázdna množina vyhovuje vždy. Nájdite vyhovujúcu množinu, ktorá bude čo najväčšia. Ak je takých viacero, vypíšte ľubovoľnú z nich. Na prvom riadku výstupu je počet účastníkov párty. Na druhom riadku výstupu je zoznam účatníkov. Títo majú byť vypísaní v rastúcom poradí a jednotlivé čísla majú byť oddelené práve jednou medzerou.

Príklad

Vstup

Výstup

4 4 2
1 2
2 3
3 1
4 1
3
1 2 3

Vstup

Výstup

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

Vstup

Výstup

9 8 2
1 7
1 5
2 8
2 5
4 9
6 4
2 7
2 1
4
1 2 5 7
Ak chceš riešiť túto úlohu, musíš sa najprv prihlásiť.