← 返回题目列表

Codeforces · 717/H

H. 扑克怪兽联盟挑战

中文机器翻译题面 查看原题

欢迎来到 Pokermon 的世界,这是一种黄色的小老鼠生物,他们非常喜欢玩扑克!

是的,对……

在接下来的扑克牌联赛中,有 n 名注册扑克牌训练师,以及 t 个现有训练师团队,每个团队属于两个联盟之一。由于训练师之间存在很多嫉妒,因此有一对互相憎恨的训练师。他们的仇恨是相互的,其中没有完全相同的对,也没有训练家讨厌自己(扑克牌的世界是一个快乐的地方!)。每个教练都有一个他想加入的球队的愿望清单。

您的任务是将玩家分为团队,并将团队分为两个会议,以便:

- 每个训练师都属于一个团队;
- 没有球队同时参加两个联盟;
- 会议之间的总仇恨至少为 e / 2;
- 每个教练都在他的愿望清单中的团队中。

会议之间的总仇恨度计算为来自不同会议的团队中彼此仇恨的培训师对的数量。

输入

输入的第一行包含两个整数 n (4 ≤ n ≤ 50 000) 和 e (2 ≤ e ≤ 100 000) – 扑克牌训练师的总数和互相讨厌的训练师对的数量。

Pokermon训练师的编号为1到n。接下来的 e 行包含两个整数 a 和 b (1 ≤ a, b ≤ n) 表示 Pokermon 训练师 a 和 b 互相讨厌。接下来的 2n 行采用以下格式。从 Pokermon 训练师 1 开始,对于每个训练师按连续顺序:第一个数字 li (16 ≤ li ≤ 20) - Pokermon 训练师愿望清单的大小,然后是 li 正整数 ti, j (1 ≤ ti, j ≤ T),提供第 i 个训练师想要加入的团队。

每个教练的愿望清单将包含每个团队不超过一次。愿望清单上的球队的编号方式是,出现在至少 1 个愿望清单上的所有球队的集合是连续正整数的集合 {1, 2, 3, …, T}。这里 T 可能高达 1 000 000。

输出

打印两行。第一行应包含 n 个数字,指定每个训练师所在的团队。

第二行应包含 T 编号,指定每个团队的会议(1 或 2)。

示例

输入 #1

4 3
1 2
2 3
4 1
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 19
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 19

输出 #1

16 15 19 14
2 2 2 1 1 1 2 1 1 2 1 1 1 2 2 1 1 1 1