Несколько лет назад тот же автор предложил для школьного соревнования следующую задачу: удалить две смежные вершины из заданного связного неориентированного графа с минимальной степенью не меньше $2$ так, чтобы сохранить связность. Но для студенческого соревнования в 2020 году эта задача слишком проста, поэтому предлагаем следующую.

Дан связный неориентированный граф, содержащий не менее $3$ вершин, без петель и кратных рёбер. Для каждого ребра определите, сохраняется ли связность графа при удалении обоих его концов.

Обратите внимание, что в этой задаче граф может содержать вершины степени $1$, но не вершины степени $0$ (поскольку он связен и содержит не менее $3$ вершин).

Входные данные

Первая строка входных данных содержит два целых числа $n$ и $m$ ($3 \le n \le 3 \cdot 10^5$; $n-1 \le m \le 3 \cdot 10^5$): количество вершин и количество рёбер соответственно. В $i$-й из следующих $m$ строк записаны два целых числа $x$ и $y$, разделённые пробелом: концы $i$-го ребра ($1 \le x,y \le n$; $x \ne y$). Гарантируется, что граф связен и не содержит кратных рёбер.

Выходные данные

Выведите одну двоичную строку длины $m$: $i$-й символ ответа должен быть «0» (без кавычек), если удаление концов $i$-го ребра делает граф несвязным, и «1» в противном случае.

Примеры

Входные данные 1

4 4
1 2
2 3
3 1
4 1

Выходные данные 1

0101

Примечание

Обратите внимание, что удаляется не только само ребро, но и оба его конца. Поэтому рассматриваемая задача отличается от поиска мостов.

Например, в примере ребро $1$–$2$ не является мостом, однако удаление вершин $1$ и $2$ делает граф несвязным: полученный граф состоит из двух изолированных вершин $3$ и $4$.

С другой стороны, ребро $1$–$4$ является мостом, однако после удаления вершин $1$ и $4$ граф остаётся связным: полученный граф состоит из двух вершин $2$ и $3$, соединённых ребром $2$–$3$.