Egy ország úthálózata $N$ városból és bizonyos városokat összekötő kétirányú utakból áll. Bármely városból bármely másik városba el lehet jutni közvetlenül vagy közvetve. Egy áruházlánc újonnan érkezett az országba, és szeretne pontosan $N/2$ áruházat építeni úgy, hogy minden városból legfeljebb egy szomszédos városig kelljen utazni, ha náluk szeretnénk bevásárolni. Más szóval, ha egy városban nem épül áruház, akkor legalább egy szomszédos városban kell majd építeni. Írjunk programot, amely megadja, hogy mely városokban legyen áruház.
A standard bemenet első sora a városok $N$ számát és az utak $M$ számát tartalmazza. A következő $M$ sor mindegyike egy-egy út által összekötött két város sorszámát tartalmazza (a városokat 1 és $N$ közötti egész számokkal azonosítjuk).
A standard kimenet első és egyetlen sora pontosan $N/2$ azonosítószámot tartalmazzon, az építendő áruházak városainak sorszámát. Több megoldás esetén bármelyik megadható.
Korlátok: $2\le N\le 100000$, páros szám; $1\le M\le 1000000$. Időlimit: 1 mp; memórialimit: 256 MB.