Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or to the problem setter(s) who authorized BZOJ to use it. If you are a copyright owner and believe that we have infringed your rights, please contact us.

Yu Xun’s homeroom teacher, Mr. Anyuan, is a very strict teacher. After entering university, it is inevitable that some ambiguous relationships may appear between boys and girls, but this obviously affects studying. Therefore, as a signature feature of Eliston, Mr. Anyuan certainly wants to prevent such situations from appearing and spreading.

So whenever Mr. Anyuan finds a boy and a girl walking together after school, or boys and girls passing notes to each other, he immediately stops them and notifies their parents. He also requires all boys and girls to turn off their phones after 8 p.m., and he calls from time to time to check. As a result, his students often sigh: this is not university, not university.

Problem Description

Among Mr. Anyuan’s students, there are $n$ boys and $n$ girls, and they are all numbered from $1\sim n$. There are $m$ pairs of boys and girls that have an ambiguous relationship. Now Mr. Anyuan wants to find a group of boys and girls such that every boy in the group has an ambiguous relationship with every girl in the group, and the total number of boys and girls is as large as possible. Note that the number of boys or the number of girls may be $0$.

If there are multiple such groups, Mr. Anyuan will choose the one with the most boys, because he thinks boys are more likely to cause trouble. If the group is still not unique, he will choose any one.

Next, from all ambiguous relationships inside the chosen group, Mr. Anyuan selects $k$ relationships to investigate, such that every boy and every girl in the group is involved in at least one of the selected relationships (i.e., is the boy or girl in that relationship). Mr. Anyuan wants you to tell him the remainder of the total number of valid ways modulo $19921228$.

Input Format

The first line contains two positive integers $n$ and $k$, representing the number of boys/girls, and the number of ambiguous relationships Mr. Anyuan will choose.

The second line contains a positive integer $m$, representing the total number of ambiguous relationships. The next $m$ lines each contain two integers, representing the indices of a boy and a girl who have an ambiguous relationship.

Output Format

The first line contains two integers separated by two spaces, representing the numbers of boys and girls in the selected group. The second line contains one integer, representing the remainder of the number of ways modulo $19921228$.

3 2 
4
1 1
1 2
2 1
2 2

2 2
2

Hint

For all data, $1\leq n \leq 50$, $1\leq m,k \leq 2500$. The same pair of ambiguous relationship will not appear more than once in the input.

Translated by ChatGPT 5