Кілька років тому цей самий автор запропонував таку задачу для шкільного змагання: видалити дві суміжні вершини із заданого зв'язного неорієнтованого графа з мінімальним степенем не менше $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$.