Hace varios años, el mismo autor propuso el siguiente problema para una competición escolar: eliminar dos vértices adyacentes de un grafo no dirigido conexo dado, cuyo grado mínimo es al menos $2$, de manera que se conserve la conectividad. Pero ese problema es demasiado sencillo para una competición de estudiantes en 2020, así que aquí vamos.

Se te da un grafo no dirigido conexo con al menos $3$ vértices, sin bucles ni aristas múltiples. Para cada arista, determina si eliminar sus dos extremos conserva la conectividad del grafo.

Observa que, en este problema, el grafo puede contener vértices de grado $1$, pero no de grado $0$ (ya que es conexo y tiene al menos $3$ vértices).

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $m$ ($3 \le n \le 3 \cdot 10^5$; $n - 1 \le m \le 3 \cdot 10^5$): el número de vértices y el número de aristas, respectivamente. La $i$-ésima de las siguientes $m$ líneas contiene dos enteros $x$ e $y$ separados por un espacio: los extremos de la $i$-ésima arista ($1 \le x, y \le n$; $x \ne y$). Se garantiza que el grafo es conexo y no contiene aristas múltiples.

Salida

Imprime una única cadena binaria de longitud $m$: el $i$-ésimo carácter de la respuesta debe ser «0» (sin comillas) si eliminar los extremos de la $i$-ésima arista hace que el grafo deje de ser conexo, y «1» en caso contrario.

Ejemplos

Entrada 1

4 4
1 2
2 3
3 1
4 1

Salida 1

0101

Nota

Ten en cuenta que no solo se elimina la propia arista, sino también sus dos extremos. Por lo tanto, esta tarea es diferente de encontrar puentes.

Por ejemplo, en el ejemplo dado, la arista $1$–$2$ no es un puente, pero eliminar los vértices $1$ y $2$ hace que el grafo deje de ser conexo: el grafo resultante consta de dos vértices aislados, $3$ y $4$.

Por otro lado, la arista $1$–$4$ es un puente, pero eliminar los vértices $1$ y $4$ deja un grafo conexo: el grafo resultante consta de dos vértices, $2$ y $3$, unidos por la arista $2$–$3$.