#P3450. [POI2006] ZOS-Sophie

[POI2006] ZOS-Sophie

题目背景

感谢uid=45443提供的翻译

此题需要spj,征求spj ing

题目描述

Little Sophie gives a birthday party. She has written a tentative list of her kindergarten friendsshe would like to invite. However, kids are very demanding guests. Mary said she should come, butonly provided Camille and Emily are not present, for they took her doll last week. Little Christopheronly plays with Sophie and Camille and he does not wish to see any other kids at the party. And soon...

Sophie considers a party a success if none of the guests invited has objection against any other'spresence. She has decided not to invite certain kids to assure that the party is a success. On theother hand she would like to invite as many kids as possible. Should Sophie not be able to invite atleast kk kids she won't give any party at all.

Task

Help little Sophie! Write a programme which:

  • reads the number of all Sophie's acquaintances nn, the number kk and a description of kids' demands from the standard input,

  • verifies if it is possible to invite at least kk kids so that the party could be a success,

  • if it is not possible, writes the word NIE (i.e. no in Polish) to the standard output; if it is possible, finds the largest group of kids who could be invited to the party so that it is a success and writes it to the standard output.

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

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

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

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

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

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

输入格式

The first line of the standard input contains two positive integers separated by a single space:

nn - the number of all Sophie's acquaintances (2n100 0002 \le n \le 100\ 000) and kk -the minimal number of kids Sophie wishes to invite to the party(n10k<nn-10 \le k < n). The kids are assigned numbers from therange 11 to nn.

The following lines contain a description of kids' demands. In the second line there is a singleinteger mm, 1m3 000 0001 \le m \le 3\ 000\ 000

Each of the following mm lines contains a pair of integers aa, bb, separated by a single space (1a,b,n,ab1 \le a,b, \le n, a \neq b). You can assume that each (ordered) pair appears in the standard input once at the most. The pair aa, bb denotes that the child aa does not wish to meet child bb at the party.

标准输入流的第一行是两个整数 nnkk2n102\le n\le10n10k<nn-10\le k<n)。表示孩子的总数和派对的最少人数。接下来一行是一个整数 mm 表示孩子们的要求(1<=m<=30000001<=m<=3000000)。

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

输出格式

If it is not possible to invite kk kids to the party so that it is a success then the first and only line ofthe standard output should contain a single word: NIE.

If it is possible, then the first line of the standard input should contain a single integer - themaximal number of kids that can be invited to the party so that it is a success.

The second line of the standard output should contain the numbers of kids to be invited, separated by single spaces, inincreasing order. Should there be more correct answers your programme should write out any oneof them.

如果不可能有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