소피의 생일 파티

어린 소피가 생일 파티를 열려고 유치원 친구들의 초대 명단을 임시로 적었습니다. 그런데 아이들은 요구가 많습니다. 어떤 아이는 특정한 다른 아이가 오면 자기는 오지 않겠다고 합니다. 예를 들어 메리는 지난주에 자기 인형을 가져간 카미유와 에밀리가 없을 때만 오겠다고 하고, 어린 크리스토퍼는 소피와 카미유하고만 놀고 싶어서 다른 아이는 아무도 보고 싶어 하지 않습니다.

이런 요구를 반대라고 부르겠습니다. 반대 $(a, b)$ 는 아이 $a$ 가 파티에서 아이 $b$ 를 만나고 싶어 하지 않는다는 뜻입니다. 소피는 초대된 어떤 손님도 다른 초대된 손님에 대해 반대하지 않을 때에만 파티가 성공이라고 봅니다. 즉 아이 $a$ 가 $b$ 를 반대하거나 아이 $b$ 가 $a$ 를 반대하면, $a$ 와 $b$ 를 동시에 초대할 수 없습니다.

소피는 파티를 성공시키기 위해 일부 아이를 초대하지 않기로 했지만, 되도록 많은 아이를 초대하고 싶습니다. 만약 아이를 $k$ 명 이상 초대할 수 없다면 파티를 아예 열지 않습니다.

모든 반대가 주어질 때, 파티가 성공하도록 소피가 초대할 수 있는 아이의 최대 수를 구하거나, $k$ 명 이상 초대하는 것이 불가능함을 판정하세요.

첫째 줄에 두 정수 $n$ 과 $k$ 가 공백으로 구분되어 주어집니다. $n$ 은 소피가 아는 아이의 수이고 $k$ 는 소피가 초대하고 싶은 최소 인원으로, $2 \le n \le 10^6$ 이고 $n - 10 \le k < n$ 입니다. 아이들은 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다.

둘째 줄에 반대의 개수 $m$ 이 주어집니다 ($1 \le m \le 3 \times 10^6$).

이어지는 $m$ 개의 줄에는 각각 두 정수 $a$ 와 $b$ 가 공백으로 구분되어 주어집니다 ($1 \le a, b \le n$, $a \ne b$). 이는 아이 $a$ 가 파티에서 아이 $b$ 를 만나고 싶어 하지 않는다는 뜻입니다. 각 순서쌍은 많아야 한 번 나타납니다.

파티가 성공하도록 아이를 $k$ 명 이상 초대하는 것이 불가능하면, 한 줄에 NIE 를 출력합니다.

가능하다면, 파티가 성공하도록 초대할 수 있는 아이의 최대 수를 정수 하나로 출력합니다.