Когда граф перестанет быть двудольным

Рёбра неориентированного графа добавляются по одному. Определите номер ребра, после добавления которого граф впервые перестаёт быть двудольным, или 0, если этого не происходит.

В первой строке $n$ и $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 3 \cdot 10^5$). В каждой из следующих $m$ строк — числа $a_i$ и $b_i$: ребро, добавляемое $i$-м по счёту. Петли и кратные рёбра возможны.

Выведите номер первого ребра, после которого граф перестал быть двудольным, или 0.