#3176. 「IOI2019」景点划分

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

巴库有 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 行两个整数 p_i,q_i ,表示编号为 p_i 的景点和编号为 q_i 的景点之间有一条双向道路。

输出格式

输出一行 n 个整数,每两个整数之间用一个空格隔开。如果不存在合法的划分,输出的 n 个整数均为 0 。否则,对于输出的第 i 个整数 s_i ,应为 1,2 3 中的一个,表示景点 i-1 被归到集合 A,B C

样例

样例输入 1

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 1 3 1 2 2 3 1 3

样例说明 1

split1.png

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

样例输入 2

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

样例输出 2

0 0 0 0 0 0

样例说明 2

split2.png

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

数据范围与提示

对于所有数据:

  • 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
  • 每一对景点之间至多有一条道路;
  • 经由这些道路,可以在任意两处景点之间往来;
  • 对于 1\le i\le m ,有 0\le p_i,q_i\le n-1 p_i\neq q_i

详细子任务附加限制与分值如下表:

子任务编号 附加限制 分值
1 每处景点至多可做两条道路的端点 7
2 a=1 11
3 m=n-1 22
4 n\le 2.5\times 10^3,m\le 5\times 10^3 24
5 没有任何附加限制 36