Description

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

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

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

Input Format

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

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

Output Format

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

3 2 
4
1 1
1 2
2 1
2 2

2 2
2

Hint

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