Há vários anos, o mesmo autor propôs o seguinte problema para uma competição escolar: eliminar dois vértices adjacentes de um dado grafo conexo não orientado, com grau mínimo de pelo menos $2$, de forma a preservar a conexidade. Mas esse problema é demasiado simples para uma competição de estudantes em 2020, por isso aqui vamos nós.

É dado um grafo conexo não orientado com pelo menos $3$ vértices, sem laços nem arestas múltiplas. Para cada aresta, determine se eliminar ambas as suas extremidades preserva a conexidade do grafo.

Observe que, neste problema, o grafo pode conter vértices de grau $1$, mas não vértices de grau $0$ (pois é conexo e tem pelo menos $3$ vértices).

Entrada

A primeira linha da entrada contém dois inteiros $n$ e $m$ ($3 \le n \le 3 \cdot 10^5$; $n - 1 \le m \le 3 \cdot 10^5$): o número de vértices e o número de arestas, respetivamente. A $i$-ésima das $m$ linhas seguintes contém dois inteiros separados por um espaço, $x$ e $y$: as extremidades da $i$-ésima aresta ($1 \le x, y \le n$; $x \ne y$). É garantido que o grafo é conexo e não contém arestas múltiplas.

Saída

Imprima uma única cadeia binária de comprimento $m$: o $i$-ésimo caráter da resposta deve ser «0» (sem aspas) se eliminar as extremidades da $i$-ésima aresta tornar o grafo desconexo, e «1» caso contrário.

Exemplos

Entrada 1

4 4
1 2
2 3
3 1
4 1

Saída 1

0101

Nota

Observe que não se elimina apenas a própria aresta, mas também ambas as suas extremidades. Portanto, a tarefa em questão é diferente de encontrar pontes.

Por exemplo, no exemplo apresentado, a aresta $1$–$2$ não é uma ponte, mas eliminar os vértices $1$ e $2$ torna o grafo desconexo: o grafo resultante consiste em dois vértices isolados, $3$ e $4$.

Por outro lado, a aresta $1$–$4$ é uma ponte, mas eliminar os vértices $1$ e $4$ torna o grafo conexo: o grafo resultante consiste em dois vértices, $2$ e $3$, ligados pela aresta $2$–$3$.