「MCOI-04」Dream SMP
题目背景
**本题为提交答案题。**
链接：https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
提取码：inbj
题目描述
Dream SMP 可以看做 $n$ 个编号为 $0,1,\dots,n-1$ 的地区。
Dream 希望将这 $n$ 个地区划分为 $8$ 个编号为 $0,1,\dots,7$ 的国家。每一个地区都所在恰好一个国家，但国家可以不包含任何地区。
地区提出 $m$ 组对划分方案的条件，其中第 $i$ 组条件用四个参数 $(u_i,a_i,v_i,b_i)$ 表示。某个划分方案合法当且仅当对所有条件，$u_i$ 号地区不属于 $a_i$ 号国家 **或者** $v_i$ 号地区不属于 $b_i$ 号国家。这里 **或者** 是逻辑或。
Dream 保证存在至少一个合法划分方案，请你构造一个合法划分方案。
输入输出格式
输入格式
第一行两个正整数 $n$ 和 $m$。
接下来 $m$ 行，每行四个正整数 $u_i,a_i,v_i,b_i$。
输出格式
输出一个长度为 $n$ 的字符串。
字符串的第 $i$ 位为 $i$ 号地区所属的国家。
输入输出样例
输入样例 #1
5 600
0 5 1 4
2 3 2 2
0 4 0 4
1 7 4 7
4 6 1 3
4 2 2 4
2 3 0 7
0 3 2 1
4 4 2 1
2 3 0 6
4 5 0 3
1 2 4 6
2 0 1 4
1 6 2 3
2 2 0 6
4 3 1 7
3 6 2 5
3 0 2 6
3 7 1 7
1 2 2 2
1 7 3 7
2 6 4 2
3 0 2 3
1 1 2 0
2 1 2 3
0 5 3 3
4 0 1 1
0 5 3 7
2 6 0 4
3 1 4 3
1 1 2 5
3 6 0 2
0 4 3 1
1 7 2 4
3 4 3 3
1 0 3 7
3 5 0 2
0 4 0 1
3 0 3 6
4 2 0 5
3 3 1 7
1 5 2 3
4 5 0 0
3 0 1 5
1 5 0 3
2 0 2 1
2 6 3 6
2 4 3 2
1 2 2 5
2 1 0 5
1 2 4 1
2 7 4 6
0 5 0 6
3 6 2 2
1 7 1 7
0 1 4 4
1 6 0 2
1 6 1 0
1 4 0 7
0 7 4 5
0 4 2 1
3 7 0 7
3 0 2 1
3 3 3 6
0 2 1 0
0 6 2 2
4 1 2 0
2 7 1 6
1 0 2 1
4 3 3 0
0 7 3 5
1 3 3 5
3 0 4 0
4 6 1 4
2 3 2 7
1 0 3 2
0 3 3 7
0 2 1 2
3 1 0 6
0 1 2 7
3 4 3 0
4 7 3 6
2 5 4 3
3 4 0 7
2 0 0 2
1 4 1 6
0 7 0 3
2 4 2 4
2 2 2 1
4 2 0 4
2 7 3 4
4 6 0 6
2 4 0 4
2 2 1 1
4 7 0 1
4 0 1 0
1 1 1 1
3 4 2 4
0 4 1 0
0 0 0 3
3 3 2 5
1 0 4 0
3 3 2 1
3 7 4 6
0 1 1 2
3 4 0 3
1 1 2 7
2 7 1 7
1 5 4 4
4 4 3 0
2 2 0 3
0 1 0 6
1 2 2 0
0 4 0 5
3 0 0 2
3 6 2 7
1 4 2 1
1 6 3 7
3 1 2 5
2 0 1 3
1 6 3 6
2 1 0 4
4 5 3 5
4 4 3 2
2 5 2 1
3 6 1 0
4 4 0 3
2 0 0 7
2 4 1 4
3 4 2 0
3 6 0 7
0 5 1 5
0 3 0 1
1 2 3 0
0 1 2 4
4 5 2 7
1 5 4 0
0 4 2 3
0 7 3 1
2 5 0 1
3 1 2 3
2 6 2 5
2 1 3 2
3 1 2 6
0 2 4 5
2 7 4 1
0 0 4 7
1 6 1 7
4 4 3 7
1 5 3 7
2 3 0 5
3 0 1 4
3 0 4 6
2 5 4 2
2 7 2 3
0 1 2 6
1 7 0 2
1 1 4 6
3 0 0 4
2 5 3 0
4 6 0 0
2 4 2 3
0 3 4 1
4 5 4 5
1 5 4 3
0 5 4 1
0 3 0 4
4 5 3 0
3 2 1 4
2 6 2 2
0 6 3 6
4 2 1 0
2 1 2 0
3 4 4 7
2 1 2 1
0 5 2 4
2 7 4 3
4 7 1 6
3 6 0 3
0 1 3 4
2 6 2 4
2 2 2 3
4 5 1 5
1 4 0 6
2 6 4 1
2 0 2 7
4 5 2 4
2 7 4 4
3 7 3 2
2 5 1 2
0 2 4 1
4 7 3 4
0 1 1 3
4 1 1 6
1 1 1 4
2 7 1 2
1 4 0 0
2 0 4 2
0 3 2 7
2 5 2 6
0 5 4 4
4 0 2 3
2 4 0 3
4 5 2 1
4 4 4 0
2 5 3 6
3 1 4 5
1 6 4 7
0 2 3 4
0 1 4 7
1 5 3 4
0 6 1 0
2 7 2 2
0 4 2 4
4 2 2 7
4 5 2 3
0 3 1 1
0 3 4 0
0 4 2 7
0 3 2 0
3 0 1 7
0 1 1 1
3 4 0 4
2 3 1 6
4 4 0 2
4 2 2 5
4 4 4 5
1 1 2 4
1 1 0 1
0 7 2 5
0 5 1 3
3 2 4 6
4 0 0 4
3 1 3 2
2 3 1 2
0 1 1 5
4 5 3 7
2 0 3 3
0 2 0 3
1 5 3 1
1 4 2 4
1 5 1 1
1 0 1 4
0 7 2 1
0 5 0 2
3 4 1 3
1 7 3 0
3 3 4 5
3 5 4 2
3 4 3 6
3 4 3 7
3 4 3 4
1 7 2 3
4 4 4 2
1 7 4 4
1 3 1 6
4 3 4 2
1 5 2 1
1 5 2 2
2 5 4 5
1 5 2 4
3 6 0 5
3 2 0 6
4 4 1 4
4 0 4 0
0 4 4 3
2 4 3 5
4 1 3 6
2 4 4 3
4 3 2 0
3 5 3 1
1 7 0 6
0 2 4 7
3 0 0 3
1 4 0 2
4 5 1 7
3 1 0 4
0 1 0 2
4 1 1 3
0 3 3 3
2 2 4 2
4 3 4 1
4 5 2 0
1 6 2 6
1 1 2 1
4 6 2 2
1 7 2 0
0 4 3 0
0 3 2 5
2 2 3 0
3 6 2 3
0 7 3 3
0 5 0 4
3 7 1 5
4 5 0 5
4 1 0 4
1 7 0 7
3 4 1 7
0 0 2 5
1 3 3 0
2 1 3 0
2 6 0 3
0 5 1 7
0 6 1 6
1 1 0 5
2 7 2 5
0 3 4 5
4 0 3 1
3 2 1 0
2 6 0 2
1 4 3 7
1 6 2 5
1 4 4 4
3 5 4 4
1 1 4 3
2 1 1 3
4 2 1 7
4 6 1 0
1 0 3 4
1 1 3 1
1 6 0 6
3 7 1 1
0 0 2 4
4 0 1 5
0 2 2 2
2 0 1 5
1 0 4 5
3 0 1 2
0 1 0 1
0 3 0 2
4 7 3 2
4 4 3 3
1 5 4 7
2 2 0 2
2 4 0 7
4 1 1 4
4 5 4 2
4 4 1 1
1 7 1 2
3 2 3 5
3 6 1 7
4 1 2 2
1 1 3 5
3 1 2 4
3 1 4 0
4 6 0 5
1 5 3 5
3 1 2 1
3 0 3 4
4 4 4 4
1 5 1 0
4 0 4 3
1 4 3 3
4 7 4 0
4 5 4 1
1 5 3 2
0 6 0 1
0 6 3 7
1 3 1 4
4 0 1 4
2 1 3 3
4 1 2 6
1 0 1 3
4 7 0 4
0 0 0 0
2 5 1 0
2 3 0 0
1 6 1 2
0 2 0 5
3 7 4 5
2 3 1 4
2 3 3 1
0 2 3 1
4 7 3 0
4 5 4 0
3 3 4 7
3 4 0 2
2 7 4 2
3 0 4 7
3 0 0 0
0 4 4 7
1 4 3 5
1 1 4 2
2 3 1 0
1 0 0 2
1 1 1 0
3 5 4 3
0 6 4 3
4 4 0 5
4 4 1 0
4 3 1 2
2 4 4 0
0 5 4 0
0 0 4 1
4 2 3 7
4 5 2 5
3 7 1 4
2 1 0 6
3 1 0 5
1 3 2 7
1 3 4 7
1 4 2 5
4 4 1 7
1 1 4 0
0 5 4 2
3 3 1 6
3 1 0 3
1 3 4 1
1 2 3 1
2 1 3 5
0 0 1 7
3 4 2 2
3 6 1 5
2 7 2 7
3 5 1 5
0 4 0 6
3 2 4 7
0 6 1 4
1 0 0 7
3 1 2 0
2 3 4 0
3 1 0 1
3 3 2 0
3 5 4 0
4 7 0 2
1 2 1 0
1 6 2 0
4 2 1 1
0 0 1 1
1 0 1 1
3 7 3 6
2 4 0 1
1 2 2 7
4 3 4 5
4 2 4 6
3 7 3 7
0 7 3 7
4 5 3 3
2 6 1 5
0 3 0 6
4 7 4 7
4 0 4 5
3 4 1 5
0 2 0 7
4 1 3 5
0 5 3 0
0 5 4 5
1 0 2 6
0 4 2 5
1 3 0 3
1 5 0 2
0 0 4 5
3 3 0 5
3 2 3 1
4 1 1 0
2 4 4 1
0 6 4 1
1 1 2 3
4 6 4 3
0 5 0 0
0 4 0 2
2 3 0 4
4 7 1 5
1 6 0 5
1 7 4 2
0 2 0 4
3 5 3 0
4 6 4 1
4 6 3 1
0 0 1 6
4 2 1 6
3 1 1 4
4 7 1 3
1 6 4 0
2 5 2 3
0 2 2 1
3 7 2 0
1 0 4 7
3 5 3 4
0 0 4 6
1 7 1 1
3 5 4 5
3 3 3 7
2 2 2 7
4 2 4 3
3 6 4 0
3 5 3 6
4 6 1 5
2 7 0 3
3 3 4 4
4 2 3 4
3 1 1 3
2 0 4 0
2 3 2 1
1 7 4 0
2 3 2 4
0 4 1 2
1 7 1 4
2 6 3 4
1 3 2 4
1 4 2 3
1 4 1 2
2 0 2 5
0 7 1 0
2 7 0 1
4 1 3 0
4 1 1 5
3 1 3 6
4 4 2 3
3 0 0 1
2 4 4 5
3 1 1 2
4 3 1 6
4 0 3 5
2 4 1 0
1 3 4 4
1 1 1 2
2 6 4 0
0 6 4 4
1 0 4 4
0 4 3 4
4 5 1 2
1 1 4 7
3 2 2 5
4 7 1 2
3 7 0 0
4 4 4 1
2 7 1 3
1 0 0 1
2 1 4 7
2 0 0 5
4 6 2 3
2 5 0 7
1 6 3 3
2 6 1 7
0 1 2 1
0 7 0 0
2 1 0 3
3 0 3 5
4 3 0 4
4 3 3 7
2 6 2 1
2 4 1 1
2 3 4 5
4 3 0 1
2 2 0 4
3 0 1 3
1 2 1 3
1 7 0 3
3 3 0 0
0 6 0 7
3 1 3 0
3 6 2 6
1 1 1 3
0 5 2 7
0 0 2 3
4 0 2 0
0 1 1 4
0 4 1 6
2 2 2 4
2 0 3 6
0 5 1 0
4 1 1 1
3 6 3 4
4 3 3 2
2 3 2 5
3 1 2 2
4 0 3 0
1 3 0 4
0 7 1 6
0 1 1 0
2 6 1 0
4 2 4 7
0 0 4 0
2 5 0 6
3 5 2 7
3 2 3 6
0 0 3 5
1 2 0 2
1 0 4 6
1 4 4 0
3 4 1 0
0 5 2 1
1 3 2 1
4 7 0 6
4 3 1 1
0 6 1 1
2 2 3 1
2 2 1 0
0 2 3 7
2 0 2 4
4 4 4 6
3 4 2 6
1 0 0 5
4 0 1 3
3 4 1 2
2 1 2 4
1 3 3 7
2 1 1 1
0 0 2 6输出样例 #1
23333说明
#### 样例 1 解释
23322，23332，23333 均是合法方案。
#### 数据规模与约定
对于 $100\%$ 的数据，$1 \le n\le10^5$，$1 \le m\le10^6$。
具体特性请自行参考输入数据。
[点击下载输入数据。](https://gitee.com/w33z8kqrqk8zzzx33/dream-oi-extra/raw/master/down.zip)
如果上面这个下载不了看下面这个：
链接：https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
提取码：inbj
#### 说明
[Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) Extra
idea & solution：w33z8kqrqk8zzzx33 check：tiger2005