CF717H.Pokermon League challenge

Welcome to the world of Pokermon, yellow little mouse-like creatures, who absolutely love playing poker!

Yeah, right…

In the ensuing Pokermon League, there are n registered Pokermon trainers, and t existing trainer teams each of which belongs to one of two conferences. Since there is a lot of jealousy between trainers, there are e pairs of trainers who hate each other. Their hate is mutual, there are no identical pairs among these, and no trainer hates himself (the world of Pokermon is a joyful place!). Each trainer has a wish-list of length l__i of teams he’d like to join.

Your task is to divide players into teams and the teams into two conferences, so that:

• each trainer belongs to exactly one team;
• no team is in both conferences;
• total hate between conferences is at least e / 2;
• every trainer is in a team from his wish-list.

Total hate between conferences is calculated as the number of pairs of trainers from teams from different conferences who hate each other.

欢迎来到宝可扑克世界！这是一群黄色的小老鼠状生物，它们酷爱玩扑克！

嗯，没错……

在即将举行的宝可扑克联赛中，共有 $n$ 名注册的宝可扑克训练家，以及 $t$ 支已有的训练家队伍，每支队伍隶属于两个联盟（conference）之一。由于训练家之间存在大量嫉妒心理，因此有 $e$ 对相互憎恨的训练家。这种憎恨是相互的，这些憎恨对中不存在重复（即无序对不重复），且没有训练家憎恨自己（宝可扑克世界是一个欢乐的地方！）。每位训练家都有一份长度为 $l_i$ 的心愿队伍列表，列出了他希望加入的队伍。

你的任务是将训练家分配到队伍中，并将队伍划分到两个联盟中，使得满足以下条件：

• 每位训练家恰好属于一支队伍；
• 任何一支队伍不能同时属于两个联盟；
• 联盟间的总憎恨值至少为 $e/2$；
• 每位训练家都被分配至其心愿列表中的一支队伍。

联盟间的总憎恨值定义为：分别属于不同联盟的两支队伍中的训练家所构成的、彼此憎恨的训练家对的数量。

The first line of the input contains two integer n (4 ≤ n ≤ 50 000) and e (2 ≤ e ≤ 100 000) — the total number of Pokermon trainers and the number of pairs of trainers who hate each other.

Pokermon trainers are numbered from 1 to n. Next e lines contain two integers a and b (1 ≤ a, b ≤ n) indicating that Pokermon trainers a and b hate each other. Next 2_n_ lines are in a following format. Starting with Pokermon trainer 1, for each trainer in consecutive order: first number l__i (16 ≤ l__i ≤ 20) — a size of Pokermon trainers wish list, then l__i positive integers t__i, j (1 ≤ t__i, j ≤ T), providing the teams the i-th trainer would like to be on.

Each trainers wish list will contain each team no more than once. Teams on the wish lists are numbered in such a way that the set of all teams that appear on at least 1 wish list is set of consecutive positive integers {1, 2, 3, …, T}. Here T might be up to 1 000 000.

输入的第一行包含两个整数 $n$（$4 \leq n \leq 50\,000$）和 $e$（$2 \leq e \leq 100\,000$）——分别表示宝可梦训练家的总人数，以及彼此厌恶的训练家对数。

宝可梦训练家编号为 $1$ 至 $n$。接下来的 $e$ 行每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$），表示训练家 $a$ 与训练家 $b$ 彼此厌恶。随后的 $2n$ 行按如下格式给出：从训练家 $1$ 开始，依次为每位训练家提供信息。对第 $i$ 位训练家，首先给出一个整数 $l_i$（$16 \leq l_i \leq 20$）——即该训练家愿望清单的长度；接着是 $l_i$ 个正整数 $t_{i,j}$（$1 \leq t_{i,j} \leq T$），表示第 $i$ 位训练家希望加入的队伍编号。

每位训练家的愿望清单中，每个队伍至多出现一次。愿望清单中出现的所有队伍编号构成一个连续的正整数集合 $\{1, 2, 3, \dots, T\}$，其中 $T$ 最多可达 $1\,000\,000$。

Print two lines. The first line should contain n numbers, specifying for each trainer the team he is in.

The second line should contain T numbers, specifying the conference for each team (1 or 2).

输出两行。第一行应包含 n 个数字，表示每位教练所属的队伍编号。

第二行应包含 T 个数字，表示每支队伍所属的联盟（1 或 2）。