#P7351. 「MCOI-04」Dream SMP

「MCOI-04」Dream SMP

题目背景

本题为提交答案题。

链接:https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
提取码:inbj

题目描述

Dream SMP 可以看做 nn 个编号为 0,1,,n10,1,\dots,n-1 的地区。
Dream 希望将这 nn 个地区划分为 88 个编号为 0,1,,70,1,\dots,7 的国家。每一个地区都所在恰好一个国家,但国家可以不包含任何地区。
地区提出 mm 组对划分方案的条件,其中第 ii 组条件用四个参数 (ui,ai,vi,bi)(u_i,a_i,v_i,b_i) 表示。某个划分方案合法当且仅当对所有条件,uiu_i 号地区不属于 aia_i 号国家 或者 viv_i 号地区不属于 bib_i 号国家。这里 或者 是逻辑或。
Dream 保证存在至少一个合法划分方案,请你构造一个合法划分方案。

输入格式

第一行两个正整数 nnmm
接下来 mm 行,每行四个正整数 ui,ai,vi,biu_i,a_i,v_i,b_i

输出格式

输出一个长度为 nn 的字符串。
字符串的第 ii 位为 ii 号地区所属的国家。

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
23333

提示

样例 1 解释

23322,23332,23333 均是合法方案。

数据规模与约定

对于 100%100\% 的数据,1n1051 \le n\le10^51m1061 \le m\le10^6
具体特性请自行参考输入数据。

点击下载输入数据。

如果上面这个下载不了看下面这个:

链接:https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
提取码:inbj

说明

Minecraft OI Round 4 Extra
idea & solution:w33z8kqrqk8zzzx33 check:tiger2005