UOJ Logo Universal Online Judge

UOJ

#535. 【IOI2019】景点划分

附件下载 统计

巴库有 $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$),或者判定合法的划分不存在。如果存在多个合法的划分,你可以给出其中的任意一个。

输入格式

第一行两个整数 $n,m$,分别表示景点数与道路数;

第二行三个整数 $a,b,c$,表示集合 $A,B$ 和 $C$ 的大小;

接下来 $m$ 行,第 $i$ 行两个整数 $x_{i},y_i$,表示编号为 $x_i$ 的景点和编号为 $y_i$ 的景点之间有一条双向道路。

输出格式

输出一行 $n$ 个整数,每两个整数之间用一个空格隔开。

如果不存在合法的划分,输出的 $i$ 个整数均为 $0$。否则,对于输出的第 $i$ 个整数 ,应为 $1,2$ 或 $3$ 中的一个,表示景点 $i-1$ 被归到集合 $A,B$ 或 $C$。

样例一

input

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

output

1 1 3 1 2 2 3 1 3

explanation

样例一示意图

一个可能的正确解为 $[1,1,3,1,2,2,3,1,3]$。这个解刻画了这样的划分:$A={0,1,3,7},B={4,5}$ 和 $C={2,6,8}$。集合 $A$ 和 $B$ 是连通的。

样例二

input

6 5
2 2 2
0 1
0 2
0 3
0 4
0 5

output

0 0 0 0 0 0

explanation

样例二示意图

合法的划分不存在。因此,唯一的正确答案是 $[0,0,0,0,0,0]$。

数据范围

测试包编号限制与约定分值
$1$每处景点至多可做两条道路的端点7
$2$$a=1$11
$3$$m=n-1$22
$4$$n \le 2500,m \le 5000$24
$5$无特殊约定36

对于所有测试数据,满足 $3 \le n \le 100000,2 \le m \le 200000,1 \le a,b,c \le n,a+b+c=n$。

保证给定的图中不包含重边或自环。

时间限制: $2\texttt{s}$

空间限制: $1\texttt{GB}$