Sophie's Birthday Party

Little Sophie is throwing a birthday party and has written a tentative list of kindergarten friends she would like to invite. The kids, however, are demanding guests: some of them refuse to come if certain other kids are also invited. For example, Mary agrees to come only if neither Camille nor Emily is present, because they took her doll last week; little Christopher will only play with Sophie and Camille and does not want to see anyone else; and so on.

We describe these wishes as objections: an objection $(a, b)$ means that kid $a$ does not want to meet kid $b$ at the party. Sophie considers the party a success if no invited guest has an objection against any other invited guest. In other words, if kid $a$ objects to kid $b$ or kid $b$ objects to kid $a$, then $a$ and $b$ cannot both be invited.

Sophie will leave out some kids to make sure the party succeeds, but she wants to invite as many kids as possible. If she cannot invite at least $k$ kids, she will not hold the party at all.

Given all the objections, determine the largest number of kids Sophie can invite so that the party is a success, or decide that inviting at least $k$ kids is impossible.

The first line contains two integers $n$ and $k$ separated by a single space: $n$ is the number of Sophie's acquaintances and $k$ is the minimum number of kids she wants to invite, with $2 \le n \le 10^6$ and $n - 10 \le k < n$. The kids are numbered from $1$ to $n$.

The second line contains a single integer $m$, the number of objections, with $1 \le m \le 3 \times 10^6$.

Each of the following $m$ lines contains two integers $a$ and $b$ separated by a single space ($1 \le a, b \le n$, $a \ne b$), meaning that kid $a$ does not want to meet kid $b$ at the party. Each ordered pair appears at most once.

If it is impossible to invite at least $k$ kids so that the party is a success, print a single line containing the word NIE.

Otherwise, print a single integer: the maximum number of kids that can be invited so that the party is a success.