English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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).
[samples]
欢迎来到扑克鼠的世界，这些黄色的小老鼠生物热爱玩扑克！
是啊，没错……
在接下来的扑克鼠联赛中，有 #cf_span[n] 名注册的扑克鼠训练师，以及 #cf_span[t] 个现有的训练师队伍，每个队伍属于两个联盟之一。由于训练师之间存在大量嫉妒，因此有 #cf_span[e] 对训练师彼此憎恨。这种憎恨是相互的，这些对中没有重复，也没有训练师憎恨自己（扑克鼠的世界是一个欢乐的地方！）。每个训练师都有一个长度为 #cf_span[li] 的愿望清单，列出了他希望加入的队伍。
你的任务是将玩家分配到队伍中，并将队伍分配到两个联盟中，使得：
联盟间的总憎恨值定义为：来自不同联盟的队伍中的训练师对，且彼此憎恨的对数。
输入的第一行包含两个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 50 000]) 和 #cf_span[e] (#cf_span[2 ≤ e ≤ 100 000]) —— 分别表示扑克鼠训练师的总数和彼此憎恨的训练师对数。
扑克鼠训练师编号从 #cf_span[1] 到 #cf_span[n]。接下来的 #cf_span[e] 行每行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n])，表示训练师 #cf_span[a] 和 #cf_span[b] 彼此憎恨。接下来的 #cf_span[2n] 行格式如下：从训练师 #cf_span[1] 开始，按顺序为每个训练师提供：首先是一个整数 #cf_span[li] (#cf_span[16 ≤ li ≤ 20]) —— 表示该训练师愿望清单的大小，然后是 #cf_span[li] 个正整数 #cf_span[ti, j] (#cf_span[1 ≤ ti, j ≤ T])，表示第 #cf_span[i] 个训练师希望加入的队伍。
每个训练师的愿望清单中，每个队伍最多出现一次。队伍编号方式保证：至少出现在一个愿望清单中的所有队伍构成连续正整数集合 #cf_span[{1, 2, 3, …, T}]。这里 #cf_span[T] 最多可达 #cf_span[1 000 000]。
请输出两行。第一行应包含 #cf_span[n] 个数字，指定每个训练师所属的队伍。
第二行应包含 #cf_span[T] 个数字，指定每个队伍所属的联盟（#cf_span[1] 或 #cf_span[2]）。
## Input
输入的第一行包含两个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 50 000]) 和 #cf_span[e] (#cf_span[2 ≤ e ≤ 100 000]) —— 分别表示扑克鼠训练师的总数和彼此憎恨的训练师对数。扑克鼠训练师编号从 #cf_span[1] 到 #cf_span[n]。接下来的 #cf_span[e] 行每行包含两个整数 #cf_span[a] 和 #cf_span[b] (#cf_span[1 ≤ a, b ≤ n])，表示训练师 #cf_span[a] 和 #cf_span[b] 彼此憎恨。接下来的 #cf_span[2n] 行格式如下：从训练师 #cf_span[1] 开始，按顺序为每个训练师提供：首先是一个整数 #cf_span[li] (#cf_span[16 ≤ li ≤ 20]) —— 表示该训练师愿望清单的大小，然后是 #cf_span[li] 个正整数 #cf_span[ti, j] (#cf_span[1 ≤ ti, j ≤ T])，表示第 #cf_span[i] 个训练师希望加入的队伍。每个训练师的愿望清单中，每个队伍最多出现一次。队伍编号方式保证：至少出现在一个愿望清单中的所有队伍构成连续正整数集合 #cf_span[{1, 2, 3, …, T}]。这里 #cf_span[T] 最多可达 #cf_span[1 000 000]。
## Output
请输出两行。第一行应包含 #cf_span[n] 个数字，指定每个训练师所属的队伍。第二行应包含 #cf_span[T] 个数字，指定每个队伍所属的联盟（#cf_span[1] 或 #cf_span[2]）。
[samples]
**Definitions:**
- Let $ n $ be the number of trainers, numbered $ 1 $ to $ n $.
- Let $ e $ be the number of mutual hate pairs between trainers.
- Let $ T $ be the total number of distinct teams (from wish lists), where $ T \leq 1{,}000{,}000 $.
- Let $ H \subseteq \{ (a,b) \mid 1 \leq a < b \leq n \} $ be the set of hate pairs, with $ |H| = e $.
- For each trainer $ i \in \{1, \dots, n\} $, let $ W_i \subseteq \{1, \dots, T\} $ be his wish list of teams, with $ |W_i| = \ell_i \in [16, 20] $.
**Variables:**
- Let $ x_i \in \{1, \dots, T\} $ denote the team assigned to trainer $ i $, for $ i = 1, \dots, n $.
- Let $ c_j \in \{1, 2\} $ denote the conference assigned to team $ j $, for $ j = 1, \dots, T $.
**Constraints:**
1. **Wish List Constraint:**
For each trainer $ i $, $ x_i \in W_i $.
2. **Team Assignment Consistency:**
Each trainer is assigned exactly one team.
**Objective:**
Minimize the **total hate between conferences**, defined as:
$$
\sum_{(i,k) \in H} \mathbb{I}[c_{x_i} \ne c_{x_k}]
$$
That is, count the number of hate pairs $ (i,k) $ such that trainer $ i $ and trainer $ k $ are assigned to teams in **different** conferences.
**Output:**
- First line: $ x_1, x_2, \dots, x_n $
- Second line: $ c_1, c_2, \dots, c_T $
---
**Note:** The problem reduces to a **constrained graph partitioning** problem:
- Nodes: trainers.
- Edges: hate pairs (undirected).
- Each node must be assigned to a team from its allowed set.
- Teams are partitioned into two conferences.
- Goal: minimize the number of hate edges crossing conferences.
API Response (JSON)
{
"problem": {
"name": "H. Pokermon League challenge",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF717H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Welcome to the world of Pokermon, yellow little mouse-like creatures, who absolutely love playing poker!\n\nYeah, right…\n\nIn the ensuing Pokermon League, there are _n_ registered Pokermon trainers, and ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "欢迎来到扑克鼠的世界，这些黄色的小老鼠生物热爱玩扑克！\n\n是啊，没错……\n\n在接下来的扑克鼠联赛中，有 #cf_span[n] 名注册的扑克鼠训练师，以及 #cf_span[t] 个现有的训练师队伍，每个队伍属于两个联盟之一。由于训练师之间存在大量嫉妒，因此有 #cf_span[e] 对训练师彼此憎恨。这种憎恨是相互的，这些对中没有重复，也没有训练师憎恨自己（扑克鼠的世界是一个欢乐的地方！）。每个...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ n $ be the number of trainers, numbered $ 1 $ to $ n $.\n- Let $ e $ be the number of mutual hate pairs between trainers.\n- Let $ T $ be the total number of distinct teams (fr...",
"is_translate": false,
"language": "Formal"
}
]
}