% Автор: Сергей Копелиович
% Источник: Харьковская зимняя школа, февраль 2014

\begin{problem}{Ребра добавляются, граф растет}
{stdin}{stdout}
{0.5 секунд}{512 мегабайт}{}

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

\InputFile

На первой строке $n$ --- количество вершин, $m$ --- количество операций <<добавить ребро>>.
Следующие $m$ строк содержат пары чисел от $1$ до $n$ --- описание добавляемых ребер.

\OutputFile

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

\Scoring

\begin{tabular}{ll}
  {\bf Подзадача 1 (25 баллов)} & $1 \le n, m \le 1\,000$. \\
  {\bf Подзадача 2 (50 баллов)} & $1 \le n, m \le 50\,000$. \\
  {\bf Подзадача 3 (25 баллов)} & $1 \le n, m \le 300\,000$. \\
\end{tabular}

\Examples

\begin{example}
\exmp{
3 3
1 2
2 3
3 1
}{
110
}%
\end{example}

\end{problem}
