Data je povezana mreža n gradova i neki od gradova su međusobno povezani dvosmernim putevima. Rastojanje između dva grada se određuje kao najmanji broj puteva koje treba preći da bi stigli iz jednog grada u drugi. Za skup gradova kažemo da je k-slobodan ako je udaljenost svaka dva grada iz tog skupa strogo veća od k. Vaš zadatak je da odredite što veći k-slobodan skup.

Za ovaj zadatak potrebno je da predate izlazne datoteke za 10 ulaznih datoteka kfree.01.in, kfree.02.in, ..., kfree.10.in, koji se nalaze u arhivi na računaru. Izlazi se pamte u datoteke kfree.01.out, kfree.02.out, ..., kfree.10.out, pri čemu broj u nazivu izlazne datoteke odgovara broju u nazivu ulazne datoteke.

Ulaz:

U prvom redu se nalaze prirodni brojevi n, m i k, koji redom predstavljju broj gradova, broj puteva i parametar k ≥ 1. U sledećih m redova se nalaze po dva različita broja a i b (1 ≤ a, b ≤ n), koji predstavljaju puteve. Gradovi su oznaqeni brojevima od 1 do n.

Izlaz:

U prvom redu ispisati veličinu k-slobodnog skupa. U sledećem redu ispisati indekse gradova koji pripadaju k-slobodnom skupu.

Primer 1:

11 12 2
1 3
2 3
3 4
4 5
4 6
5 7
6 9
7 8
8 9
8 10
9 10
7 11

3
1 6 11

Objašnjenje.

Ako odaberemo gradove 1, 6 i 11 lako zaključujemo da su gradovi 1 i 11 na rastojanju 4, gradovi 1 i 6 na rastojanju 3 i gradovi 11 i 6 na rastojanju 4. Kako su sva rastojanja strogo veća od 2, dati skup je 3-slobodan.

Ocenjivanje.

Broj bodova za svaki test primer se određuje na sledeći način. Neka je VAL veličina vašeg k-slobodnog skupa, a OTP je maksimalna veličina k-slobodnih skupova među svim takmičarskim rešenjima, uključujući i komisijsko rešenje. Broj bodova za svaki test primer se računa na sledeći način: ako je OTP = VAL dobijate 10 poena, ako je OTP = VAL+1 dobijate 8 poena, ako je OTP = VAL+2 dobijate 7 poena, ako je OTP = VAL+3 dobijate 4 poena, ako je OTP = VAL + 4 dobijate 3 poena, ako je OTP = VAL + 5 dobijate 1 poen i ako je OTP ≥ VAL + 6 dobijate 0 poena.