== include(page="template/taskheader" task_id="markon") ==
Albăstrel a găsit o hartă pe care sunt reprezentate $N$ oraşe legate între ele prin $M$ tuneluri bidirecţionale. Fiecare oraş are asociat un număr natural cu o semnificaţie necunoscută lui Albăstrel. Ingenios din fire, acesta a folosit harta pentru a realiza un nou joc pe calculator. Jocul constă în marcarea oraşelor după o anumită regulă: un oraş $A$ poate fi marcat numai dacă cel puţin unul dintre oraşele sale vecine $B$, marcat deja, are una dintre proprietăţile:

$1.$ Valoarea asociată lui B este egală cu zero;
$2.$ Valoarea asociată lui B este strict mai mare decât numărul oraşelor nemarcate vecine cu B.
Două oraşe sunt considerate vecine dacă există un tunel între ele. Calculatorul alege oraşul de start  X iar  jucătorul trebuie să înceapă  marcarea cu acest oraş. Pentru a câştiga,  el trebuie să marcheze un număr maxim de oraşe de pe hartă, respectând regula jocului.

$1.$ Valoarea asociată lui $B$ este egală cu zero;
$2.$ Valoarea asociată lui $B$ este strict mai mare decât numărul oraşelor nemarcate vecine cu $B$.
Două oraşe sunt considerate vecine dacă există un tunel între ele. Calculatorul alege oraşul de start $X$ iar  jucătorul trebuie să înceapă  marcarea cu acest oraş. Pentru a câştiga, el trebuie să marcheze un număr maxim de oraşe de pe hartă, respectând regula jocului.

h2. Cerinţă

* între două oraşe diferite poate exista cel mult un tunel
* oraşul $X$ este singurul oraş care poate fi marcat prima dată
* dacă există mai multe soluţii cu număr maxim, se va afişa oricare dintre acestea

* pentru $30%$ din teste $$N$, $M$ ≤ 10.000$

* pentru $30%$ din teste $N$, $M$ ≤ $10.000$

h2. Exemplu

7518