[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 $k$ 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 $n$, the number $k$ and a description of kids' demands from the standard input, - verifies if it is possible to invite at least $k$ 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: $n$ - the number of all Sophie's acquaintances ($2 \le n \le 100\ 000$) and $k$ -the minimal number of kids Sophie wishes to invite to the party($n-10 \le k < n$). The kids are assigned numbers from therange $1$ to $n$. The following lines contain a description of kids' demands. In the second line there is a singleinteger $m$, $1 \le m \le 3\ 000\ 000$ Each of the following $m$ lines contains a pair of integers $a$, $b$, separated by a single space ($1 \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 $a$, $b$ denotes that the child $a$ does not wish to meet child $b$ at the party. 标准输入流的第一行是两个整数 $n$ 和 $k$（$2\le n\le10$，$n-10\le k<n$）。表示孩子的总数和派对的最少人数。接下来一行是一个整数 $m$ 表示孩子们的要求（$1<=m<=3000000$）。 接下来m行每行有一堆整数a和b，用空格隔开（1<=a,b<=n,a!=b）。表示第a个孩子不能和第b个孩子同时参加派对。保证有序对a，b不重复。

If it is not possible to invite $k$ 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