[AdditionalFile5509.zip](file://AdditionalFile5509.zip?type=additional_file)

#5509. 「POI2006 R3」索西娅 Sophie

标签: 传统 | 时间限制: 8500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – III etap Zosia

小索西娅正在筹办生日派对。她草拟了一份想要邀请的 $n$ 位幼儿园朋友的初步名单。然而，孩子们都非常挑剔。玛雅说，她会来，但前提是派对上没有上周抢走了她娃娃的卡米卡和艾米莉卡。小克里斯只和索西娅还有卡米卡玩，不想在派对上看到其他孩子。诸如此类……

索西娅认为，一个派对是成功的，当且仅当所有来宾都不反对其他任何一位来宾的出席。索西娅决定，为了让派对成功，她不会邀请某些孩子。另一方面，索西娅希望邀请尽可能多的孩子。她觉得，如果她不能邀请至少 $k$ 个孩子，那她就干脆不办派对了。

帮助小索西娅！编写一个程序，实现以下功能：

• 从标准输入读取索西娅所有朋友的总数 $n$、数字 $k$ 以及孩子们的要求描述，
• 检查是否可以邀请至少 $k$ 个孩子，使得派对是成功的，
• 如果不可能，则向标准输出输出 NIE；如果可能，则找到并向标准输出输出可以邀请的、能使派对成功的最大规模的儿童群体。

输入格式

输入的第一行包含两个非负整数，由单个空格隔开：$n, k$ $(2 \le n \le 1000000, n-10 \le k < n)$，分别表示索西娅所有朋友的总数和索西娅希望邀请的最少儿童数量。孩子们的编号为 $1$ 到 $n$。

接下来的行包含孩子们的要求描述。第二行是一个整数 $m$ $(1 \le m \le 3000000)$。

接下来的 $m$ 行，每行包含一对整数 $a,b$ $(1 \le a, b \le n, a \neq b)$，由单个空格隔开。你可以假设每个（有序的）数对在输入中最多出现一次。一对 $a, b$ 表示编号为 $a$ 的孩子不希望在派对上遇到编号为 $b$ 的孩子。

输出格式

如果无法邀请 $k$ 个孩子来举办一个成功的派对，那么标准输出的第一行且仅一行应只包含一个字符串 NIE。

如果可能，那么标准输出的第一行应包含一个整数，表示可以邀请来举办成功派对的最大儿童数量。此时，标准输出的第二行应包含应受邀请的孩子的编号，按升序排列并用单个空格隔开。如果存在多个正确答案，你的程序可以输出其中任意一个。

样例

输入

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

输出

5
1 3 5 6 8