bzoj#P1525. [POI2006]Zos

[POI2006]Zos

题目描述

Sophie 举办了一个生日派对,她为此写了一个不确定的表,表上是她邀请的幼儿园朋友。然而孩子们都是苛刻的客人。Mary 说她要来,但是因此 Camille 和 Emily 就不来了,因为他们上周拿走了 Mary 的娃娃。Christopher 只和 Sophie 和 Camille 一起玩,他不想在聚会上看到别的孩子。很快…

Sophie 认为如果没有反对任何人出席的客人,那这个派对就是成功的。因此她决定不邀请某些孩子来保证晚会是成功的。另一方面,她想邀请尽可能多的孩子。如果 Sophie 不能邀请至少 kk 的孩子,她根本就无法举办任何派对。

帮一下 Sophie 吧。写一个能够实现以下目标的程序:

在标准输入流中读入n和k,分别表示孩子的总数和派对的最少人数。

确定能否举办派对。如果不能,输出 NIE(即波兰语中的“否”)

如果可能的话,找一组尽可能多被邀请参加聚会的孩子,这样就成功了,并把它写在标准输出流上。

输入格式

标准输入流的第一行是两个整数 nnkk2n×1052 \le n \le \times 10^5),(n10k<nn-10 \le k < n)。表示孩子的总数和派对的最少人数。接下来一行是一个整数m表示孩子们的要求 (1m3×1061 \le m \le 3 \times 10^6)

接下来m行每行有一堆整数 aabb,用空格隔开(1a,bn,ab1 \le a,b \le n, a \neq b)。表示第 aa 个孩子不能和第 bb 个孩子同时参加派对。保证有序对 (a,b)(a,b) 不重复。

输出格式

如果不可能有 kk 个孩子参加派对,输出 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