几年前，同一位作者曾为一场学校竞赛提出了以下问题：从给定的连通无向图（最小度数至少为 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 \neq 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 相连。