#P10598. BZOJ2162 男生女生

BZOJ2162 男生女生

题目背景

题目来自原 BZOJ,我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益,可联系我们。


雨荨的班主任安远老师是一个非常严厉的老师。到了大学,男生和女生之间难免会出现一些暧昧关系,但这样显然是影响学习的。所以作为艾利斯顿的一块招牌,安远老师当然要拒绝这种现象的出现以及繁衍。

所以每当安远老师发现一个男生和一个女生放学走在一起或者男女生之间互相传纸条等,他就会立马制止并且通知家长。他也要求所有男女生晚上八点之后必须关手机,并且不定期打电话检查。于是安远老师的学生都感慨:这货不是大学,不是大学。

题目描述

安远老师的学生里,一共有 nn 个男生和 nn 个女生,编号都以 1n1\sim n 编号。有 mm 对男女生之间有暧昧关系。现在安远老师想找出这样一个男女生群体,每个男生都和每个女生之间有暧昧关系,并且男女生总数最大。注意,男生数目或者女生数目可以为 00

如果有多个这样的群体,安远老师会选择男生最多的那个群体,因为他觉得男生会很不安分。如果这样的群体依然不唯一,他会选择任意一个。

接下来,安远老师从选出的这个群体的所有暧昧关系中,选出 kk 个进行调查,使得这个群体的所有男生和女生,都至少和其中的一对暧昧关系有关系(即是这个暧昧关系的男/女主人公)。安远老师想让你告诉他总方案数除以 1992122819921228 的余数是多少。

输入格式

输入的第一行包含两个正整数 nnkk,分别代表男生女生的个数,以及安远老师要选择的暧昧关系个数。

第二行为一个正整数 mm,代表暧昧关系总个数。接下来 mm 行,每行两个整数,代表一对有暧昧关系的男女生编号。

输出格式

第一行有两个空格隔开的整数,代表选择的团体内男生和女生的个数。第二行有一个整数,代表选法除以 1992122819921228 的余数。

3 2 
4
1 1
1 2
2 1
2 2
2 2
2

提示

对于所有数据,1n501\leq n \leq 501m,k25001\leq m,k \leq 2500。同一对暧昧关系不会在输入中出现多次。