Comet OJ

C1982 [Contest #15]孤独的吉姆 6

内存限制：256 MB 时间限制：3000 ms

题目描述

省略狗血剧情，此题所求如下：

给你一个 $n$ 个点 $m$ 条边的简单连通无向图，请拔掉一些边使得图中奇数度数的点尽可能多，并输出一种方案。 (拔掉后的图不需要是连通的。)

虽然原本想要对参赛者亲切一点，输出任一种方案就好了，但不幸的，comet OJ 的 special judge 功能突然失灵了！所以你输出的解必须和出题者的作法所输出的一样！偷偷在这里告诉大家，出题者的做法，恰好是输出字典序最大的方案唷！(详情请见输出格式。)

输入格式

第一行有两个正整数 $n, m$，分别代表给定的简单连通无向图中点的个数和边的个数。

接下来有 $m$ 行，当中的第 $i$ 行有两个正整数 $x_i, y_i$，分别代表第 $i$ 条边连接编号 $x_i$ 和编号 $y_i$ 的点。点是由 $0$ 编号到 $n-1$。

  • $2 \le n \le 6 \times 10^5$

  • $n - 1 \le m \le 9 \times 10^5$

  • $0 \le x_i < y_i < n$

  • 如果 $i \ne j$, 那么 $(x_i, y_i) \ne (x_j, y_j)$

  • 给定的图为连通图

输出

请输出一行长度为 $m$ 且由数字字符 '0' 和 '1' 组成的字符串，若第 $i$ 个数字是 '0'，代表奇数度数的点最多的时候第 $i$ 条边被拔掉了；若是 '1'，则没被拔掉。

若有多种拔掉边的方法能使奇数度数的点最多，那么出题者的代码会输出字典序最大的点，而你的输出和此代码的输出一样才算答对。(若不懂如何比较字典序，请参考提示)

样例

样例输入 1

3 3
0 1
1 2
0 2

样例输出 1

110

样例输入 2

5 10
0 4
1 4
2 3
1 3
3 4
2 4
0 3
0 1
1 2
0 2

样例输出 2

1111110101

提示

假设有两个长度相同的由 '0' 和 '1' 组成的字符串 $s$ 和 $t$，我们称 $s$ 的字典序比 $t$ 大当且仅当 在 $s$ 和 $t$ 第一个字符不一样的位置上，$s$ 的该位置是 '1' 且 $t$ 的该位置是 '0'。