巴库有 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 。
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 是连通的。
6 5 2 2 2 0 1 0 2 0 3 0 4 0 5
0 0 0 0 0 0
合法的划分不存在。因此,唯一的正确答案是 [0,0,0,0,0,0] 。
对于所有数据:
详细子任务附加限制与分值如下表: