题目描述

舒钦学院的所有学生都非常有才华。每个学生都恰好精通一门外语，并且恰好会演奏一种乐器。

混合文化奥林匹亚竞赛即将开始。竞赛包含若干语言类别和若干乐器类别。一个学校在每个类别（某一种语言或某一种乐器）中至多只能派出 1 名参赛者。
然而，舒钦学院的学生都很骄傲，没有人愿意只凭其中一项能力参赛。也就是说，若某名学生进入代表队，那么代表队中不能再有其他学生与他掌握同一种语言，也不能再有其他学生与他演奏同一种乐器。

校长希望组成一个队伍，使得参赛学生数尽可能多。学生会主席白银御行想进一步知道：

• 有没有某些学生，无论怎样组出一个最大规模代表队，他们都一定会被选中；
• 有没有某些学生，在任何一个最大规模代表队中都不会被选中；
• 类似地，有没有某些语言类别 / 乐器类别，在所有最大规模代表队中都一定出现，或者在所有最大规模代表队中都一定不出现。

换句话说，在所有可能的最大规模代表队中，是否存在：

• 一定出现于所有代表队中的学生 / 语言 / 乐器；
• 一定不出现于任何代表队中的学生 / 语言 / 乐器。

请你编写程序 olympiad，回答上述问题。

输入格式

第一行输入三个整数 N, S, T，分别表示：

• N：学生人数；
• S：语言种数；
• T：乐器种数。

接下来 N 行，每行输入两个整数 L_i, M_i，表示第 i 名学生掌握的语言编号和乐器编号。

输出格式

第一行输出 7 个整数：

K, AN, BN, AL, BL, AM, BM

其中：

• K：最大规模代表队中的学生人数；
• AN, BN：分别表示“在所有最大规模代表队中一定被选中的学生数”和“在所有最大规模代表队中一定不会被选中的学生数”；
• AL, BL：分别表示“在所有最大规模代表队中一定出现的语言数”和“在所有最大规模代表队中一定不会出现的语言数”；
• AM, BM：分别表示“在所有最大规模代表队中一定出现的乐器数”和“在所有最大规模代表队中一定不会出现的乐器数”。

接下来依次输出 6 行，分别为：

1. 一定被选中的学生编号；
2. 一定不会被选中的学生编号；
3. 一定出现的语言编号；
4. 一定不会出现的语言编号；
5. 一定出现的乐器编号；
6. 一定不会出现的乐器编号。

如果某一行对应的集合为空，则输出一个空行即可。
每一行中的编号都必须按升序输出，并以单个空格分隔。

数据范围

• 1 <= N <= 1.5 × 10^5
• 1 <= S, T <= 7.5 × 10^4
• 1 <= L_i <= S
• 1 <= M_i <= T

子任务

通过某个子任务的全部测试点后，才能获得该子任务对应的全部分数。

样例

输入

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

输出

3 1 1 2 0 2 1
6
5
3 4

1 4
5

样例解释

设四种语言依次为：法语、德语、韩语、斯瓦希里语。
设五种乐器依次为：钢琴、吉他、竖琴、迪吉里杜管、单簧管。

• 第 1 名学生会法语，演奏钢琴；
• 第 2 名学生会德语，演奏钢琴；
• 第 3 名学生会韩语，演奏吉他；
• 第 4 名学生会韩语，演奏竖琴；
• 第 5 名学生会韩语，演奏迪吉里杜管；
• 第 6 名学生会斯瓦希里语，演奏迪吉里杜管。

没有任何学生会演奏单簧管。

可能的最优代表队有：

• 1, 3, 6
• 1, 4, 6
• 2, 3, 6
• 2, 4, 6

由此可见：

• 学生 6 一定会被选中；
• 学生 5 一定不会被选中；
• 语言 3, 4（韩语、斯瓦希里语）一定出现；
• 乐器 1, 4（钢琴、迪吉里杜管）一定出现；
• 乐器 5（单簧管）一定不会出现。