Delete Two Vertices Again

Several years ago, the same author proposed the following problem for a school competition: delete two adjacent vertices from a given connected undirected graph with min-degree at least $2$ so that the graph stays connected. That problem is too simple for a student competition in 2020, so here is a harder version.

You are given a connected undirected graph with at least $3$ vertices. It has no self-loops and no multiple edges. For each edge, determine whether deleting both of its endpoints keeps the graph connected.

The graph may contain vertices of degree $1$, but it has no vertices of degree $0$, because it is connected and has at least $3$ vertices.

The first line contains two integers $n$ and $m$ ($3 \leq n \leq 3 \cdot 10^5$, $n - 1 \leq m \leq 3 \cdot 10^5$), the number of vertices and the number of edges. The $i$-th of the following $m$ lines contains two space-separated integers $x$ and $y$, the endpoints of the $i$-th edge ($1 \leq x, y \leq n$, $x \neq y$). The graph is connected and has no multiple edges.

Print a binary string of length $m$. The $i$-th character is "0" if deleting the endpoints of the $i$-th edge disconnects the graph, and "1" otherwise.

Note that both endpoints of the edge are deleted, not only the edge itself. So this task is different from finding bridges.

For example, in the sample, edge $1$-$2$ is not a bridge, but deleting vertices $1$ and $2$ disconnects the graph. The remaining graph consists of two isolated vertices, $3$ and $4$. On the other hand, edge $1$-$4$ is a bridge, but deleting vertices $1$ and $4$ leaves the graph connected. The remaining vertices $2$ and $3$ are joined by edge $2$-$3$.