Kilka lat temu ten sam autor zaproponował na zawody szkolne następujące zadanie: usunąć dwa sąsiednie wierzchołki z danego spójnego grafu nieskierowanego o minimalnym stopniu co najmniej 2, tak aby zachować spójność. To zadanie jest jednak zbyt proste na zawody studenckie w 2020 roku, więc oto nowe.

Dany jest spójny graf nieskierowany o co najmniej 3 wierzchołkach, bez pętli i krawędzi wielokrotnych. Dla każdej krawędzi ustal, czy usunięcie obu jej końców zachowuje spójność grafu.

Zauważ, że w tym zadaniu graf może zawierać wierzchołki stopnia 1, ale nie stopnia 0 (ponieważ jest spójny i ma co najmniej 3 wierzchołki).

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ i $m$ ($3 \le n \le 3 \cdot 10^5$; $n - 1 \le m \le 3 \cdot 10^5$): odpowiednio liczbę wierzchołków i liczbę krawędzi. W $i$-tym z kolejnych $m$ wierszy znajdują się dwie liczby całkowite $x$ i $y$, oddzielone spacją: końce $i$-tej krawędzi ($1 \le x,y \le n$; $x \ne y$). Zagwarantowano, że graf jest spójny i nie zawiera krawędzi wielokrotnych.

Wyjście

Wypisz jeden ciąg binarny długości $m$: $i$-tym znakiem odpowiedzi powinno być „0” (bez cudzysłowów), jeśli usunięcie końców $i$-tej krawędzi sprawia, że graf staje się niespójny, a „1” w przeciwnym razie.

Przykład

Wejście 1

4 4
1 2
2 3
3 1
4 1

Wyjście 1

0101

Uwagi

Zauważ, że usuwana jest nie tylko sama krawędź, lecz także oba jej końce. Dlatego rozważane zadanie różni się od znajdowania mostów.

Na przykład w przykładzie krawędź $1$–$2$ nie jest mostem, ale usunięcie wierzchołków $1$ i $2$ sprawia, że graf staje się niespójny: powstały graf składa się z dwóch izolowanych wierzchołków $3$ i $4$.

Z drugiej strony krawędź $1$–$4$ jest mostem, ale po usunięciu wierzchołków $1$ i $4$ graf jest spójny: powstały graf składa się z dwóch wierzchołków $2$ i $3$, połączonych krawędzią $2$–$3$.