20592번 - Delete Two Vertices Again 다국어

문제

Several years ago, the same author has proposed the following problem for a school competition: delete two adjacent vertices from a given connected undirected graph with min-degree at least 2ドル$ in a way that preserves connectivity. But that problem is too simple for a student competition in 2020, so here we go.

You are given a connected undirected graph with at least 3ドル$ vertices and without self-loops and multiple edges. For each edge, determine whether deleting both its endpoints preserves connectivity of the graph.

Notice that, in this problem, the graph may contain vertices of degree 1ドル,ドル but not vertices of degree 0ドル$ (since it is connected and has at least 3ドル$ vertices).

입력

The first line of the input 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 correspondingly. 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$). It is guaranteed that the graph is connected and does not contain multiple edges.

출력

Output a single binary string of length $m$: $i$-th character of the answer should be "0" (without quotes) if deleting endpoints of the $i$-th edge makes the graph disconnected and "1" otherwise.

제한

힌트

Please notice that not only the edge itself is deleted, both its endpoints are too. Therefore, the task in question is different from finding bridges.

For example, in the sample, the edge 1ドル$--2ドル$ is not a bridge, but deleting vertices 1ドル$ and 2ドル$ makes the graph disconnected: the resulting graph consists of two isolated vertices 3ドル$ and 4ドル$.

On the other hand, the edge 1ドル$--4ドル$ is a bridge, but deleting vertices 1ドル$ and 4ドル$ makes the graph connected: the resulting graph consists of two vertices 2ドル$ and 3ドル,ドル connected by the edge 2ドル$--3ドル$.