Задача D. Ребра добавляются, граф растет

Входной файл:Стандартный вход   Ограничение времени:3.5 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб

Условие

В неориентированный граф последовательно добавляются новые ребра. Изначально граф пустой. После каждого добавления нужно говорить, является ли текущий граф двудольным.

Формат входных данных

На первой строке n — количество вершин, m — количество операций "добавить ребро". Следующие m строк содержат пары чисел от 1 до n — описание добавляемых ребер. 1 ≤ n, m ≤ 300 000.

Формат выходных данных

Выведите в строчку m нулей и единиц. i-й символ должен быть равен единице, если граф, состоящий из первых i ребер, является двудольным.

Ограничения

Примеры тестов

Стандартный вход Стандартный выход
1
3 3
1 2
2 3
3 1
110

0.060s 0.010s 13