B. Зелёный Hackenbush

Дан связный неориентированный граф; вершина $1$ — земля. За ход игрок стирает любое ребро, после чего всё, что перестало быть связано с землёй, отваливается и в игре больше не участвует. Проигрывает тот, кто не может сделать ход.

В графе могут быть петли и кратные рёбра.

В первой строке $n$ и $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$). В следующих $m$ строках по два числа — концы ребра. Граф связен; петли и кратные рёбра допускаются.

Выведите $1$, если выигрывает первый игрок, и $2$ иначе.