题目背景

滥用本题评测将封号

注：本题按照传统题方式进行评测，即，你的程序需要包含 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$ 分） 没有任何附加限制。