bzoj#P1525. [POI2006]Zos
[POI2006]Zos
题目描述
Sophie 举办了一个生日派对,她为此写了一个不确定的表,表上是她邀请的幼儿园朋友。然而孩子们都是苛刻的客人。Mary 说她要来,但是因此 Camille 和 Emily 就不来了,因为他们上周拿走了 Mary 的娃娃。Christopher 只和 Sophie 和 Camille 一起玩,他不想在聚会上看到别的孩子。很快…
Sophie 认为如果没有反对任何人出席的客人,那这个派对就是成功的。因此她决定不邀请某些孩子来保证晚会是成功的。另一方面,她想邀请尽可能多的孩子。如果 Sophie 不能邀请至少 的孩子,她根本就无法举办任何派对。
帮一下 Sophie 吧。写一个能够实现以下目标的程序:
在标准输入流中读入n和k,分别表示孩子的总数和派对的最少人数。
确定能否举办派对。如果不能,输出 NIE
(即波兰语中的“否”)
如果可能的话,找一组尽可能多被邀请参加聚会的孩子,这样就成功了,并把它写在标准输出流上。
输入格式
标准输入流的第一行是两个整数 和 (),()。表示孩子的总数和派对的最少人数。接下来一行是一个整数m表示孩子们的要求 ()
接下来m行每行有一堆整数 和 ,用空格隔开()。表示第 个孩子不能和第 个孩子同时参加派对。保证有序对 不重复。
输出格式
如果不可能有 个孩子参加派对,输出 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