幾年前，同一位作者曾在一場中學生競賽中提出以下問題：給定一張最小度數至少為 $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$），分別表示頂點數和邊數。接下來 $m$ 行中的第 $i$ 行包含兩個以空格分隔的整數 $x$ 和 $y$，表示第 $i$ 條邊的端點（$1 \le x,y \le n$；$x \ne y$）。保證圖連通且不含重邊。

輸出格式

輸出一個長度為 $m$ 的二進位字串：若刪除第 $i$ 條邊的兩個端點會使圖不連通，答案的第 $i$ 個字元應為 0（不含引號），否則應為 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$ 相連。