[IOI2019] 景点划分

# 滥用本题评测将封号 注：本题按照传统题方式进行评测，即，你的程序**需要包含 `main` 函数**。

巴库有 $n$ 处景点，从 $0$ 到 $n-1$ 编号。另外还有 $m$ 条双向道路，从 $0$ 到 $m-1$ 编号。每条道路连接两个不同的景点。经由这些道路，可以在任意两处景点之间往来。 Fatima 打算在三天之内参观完所有这些景点。她已经决定要在第一天参观 $a$ 处景点，第二天参观 $b$ 处景点，第三天参观 $c$ 处景点。因此，她要将 $n$ 处景点划分为三个集合 $A$、$B$ 和 $C$，其规模分别为 $a$、$b$ 和 $c$。每处景点恰好属于其中一个集合，因此有 $a+b+c=n$。 Fatima 想要找到这样的景点划分 $A$、$B$ 和 $C$，使得这三个集合中的至少两个是联通的。一个景点集合 $S$ 被称为是联通的，如果能够经由这些道路在 $S$ 中的任意两处景点之间往来，且不需要经过不在 $S$ 中的景点。如果满足上述要求，则景点的一个划分 $A$、$B$ 和 $C$ 被称为是合法的。 请帮助 Fatima 找到一个合法的景点划分 （给定 $a$、$b$ 和 $c$），或者判断合法的划分不存在。如果存在多个合法的划分，你可以给出其中的任何一个。 **实现细节** 你需要实现下述函数： `int [] find_split（int n,int a,int b,int c,int [] p,int [] q）` - $n$：景点的数量。 - $a$、$b$ 和 $c$：集合$A$、$B$ 和 $C$ 的期望规模。 - $p$ 和 $q$：长度为 $m$ 的数组，包含道路的端点。对每个 $i$ （$ 0 \le i \le m-1 $），$p[i]$ 和 $q[i]$ 是由道路 $i$ 连接的两处景点。 - 该函数需要返回一个长度为 $n$ 的数组。记该数组为 $s$。如果不存在合法的划分，$s$ 应当包含 $n$ 个零。否则，对于 $0 \le i \le n-1$，$s[i]$ 应为 $1$、$2$ 或 $3$ 中的一个。以分别表示景点 $i$ 被归到集合 $A$、$B$ 或 $C$

第一行，两个正整数 $n$、$m$。 第二行，三个正整数 $a$、$b$ 和 $c$。 第 $3+i$ 行 （对于 $ 0 \le i \le m-1 $） 两个正整数 $p[i]$、$q[i]$。 意义见题目描述

共一行，内容为 `find_split` 所返回的数组。

9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6

1 1 3 1 2 2 3 1 3

**样例说明**  一个可能解为 $[1,1,3,1,2,2,3,1,3]$。这个解刻画了这样的划分：$A=\{0,1,3,7\}$，$B=\{4,5\}$，$C=\{2,6,8\}$。集合 $A$ 和 $B$ 是联通的。 **数据范围** 对于 $100\%$ 的数据， - $3 \le n \le 10^5$。 - $2 \le m \le 2 \times 10^5$。 - $1 \le a,b,c \le n$。 - $a+b+c=n$。 - 每一对景点之间至多有一条道路。 - 经由这些道路，可以在任何两处景点之间往来。 - 对于 $0 \le i \le m-1$，有 $0 \le p[i],q[i] \le n-1$ 和 $p[i] ≠ q[i] $。 **子任务** 1. （$7$ 分） 每处景点至多可做两条道路的端点。 2. （$11$ 分） $a=1$ 3. （$22$ 分） $m=n-1$ 4. （$24$ 分） $n \le 2500$，$m \le 5000$。 5. （$36$ 分） 没有任何附加限制。