小苏菲要举办生日派对。她列出了一份初步的幼儿园朋友邀请名单。然而，孩子们作为客人非常挑剔。玛丽说她会来，但前提是卡米尔和艾米丽不在场，因为她们上周拿走了她的洋娃娃。小克里斯托弗只和苏菲及卡米尔玩，他不希望在派对上见到其他任何孩子。诸如此类……

如果受邀的客人中没有任何人对其他人的出席有异议，苏菲就认为派对是成功的。为了确保派对成功，她决定不邀请某些孩子。另一方面，她希望尽可能多地邀请孩子。如果苏菲无法邀请至少 $k$ 个孩子，她将取消派对。

请帮助小苏菲！编写一个程序，完成以下任务：

• 从标准输入读取苏菲所有熟人的数量 $n$、数量 $k$ 以及孩子们的要求描述；
• 验证是否有可能邀请至少 $k$ 个孩子，使得派对能够成功；
• 如果不可能，向标准输出写入单词 NIE（波兰语中的“不”）；如果可能，找到可以邀请到派对上的最大孩子群体，使得派对成功，并将结果写入标准输出。

输入格式

标准输入的第一行包含两个由空格分隔的正整数：$n$ ——苏菲所有熟人的数量（$2 \le n \le 1\,000\,000$），以及 $k$ ——苏菲希望邀请到派对上的最少孩子数量（$n-10 \le k < n$）。孩子们被分配了从 $1$ 到 $n$ 的编号。

接下来的行包含孩子们的要求描述。第二行包含一个整数 $m$（$1 \le m \le 3\,000\,000$）。接下来的 $m$ 行，每行包含一对由空格分隔的整数 $a$ 和 $b$（$1 \le a, b \le n$，$a \ne b$）。你可以假设每对（有序）数对在标准输入中最多出现一次。数对 $a, b$ 表示孩子 $a$ 不希望在派对上见到孩子 $b$。

输出格式

如果无法邀请 $k$ 个孩子使得派对成功，则标准输出的第一行（也是唯一一行）应包含一个单词：NIE。

如果可能，标准输出的第一行应包含一个整数，即可以邀请到派对上且使派对成功的最大孩子数量。标准输出的第二行应包含受邀孩子的编号，按升序排列，并用空格分隔。如果有多个正确的答案，你的程序只需输出其中任意一个。

样例

样例输入 1

9 4
12
9 6
4 6
7 9
1 2
2 1
9 7
7 6
4 5
7 8
8 9
3 4
4 3

样例输出 1

5
1 3 5 6 8