Problem : 98 - 慶功宴

Special Judge

Problem Statistics

Solved Member: 9　　Submission: 51　　User Tried: 11

Statement:

在成功佔領宇宙的慶功宴上，兔王決定邀請他的愚民們一起參加。
國家共有 N 位人民，由 1 標號到 N，兔王希望至少邀請到 K 位人民來到他的宴會上，並且，好大喜功的兔王希望越多人參加越好。

由於人民之間可能存在著討厭的關係，例如 A 討厭 B，若 A 與 B 一起參加宴會的話，變會一發不可收拾。
身為一國之君，兔王當然不希望發生一發不可收拾的事件來使自己顏面掃地。

目前你已經知道了人民們互相討厭的狀態了，兔王想知道他最多能邀請多少人，能不能滿足他的要求呢？

Input:Output:

第 1 行有兩個數字 N,K (2 ≤ N ≤ 1000000, N-10 ≤ K ≤ N)，代表人民總數以及兔王至少想要邀請的人數。
第 2 行有一個正整數 M(1 ≤ M ≤ 3000000)，代表人民間存在這麼多個互相討厭的關係。
第 3 行之後的 M 行，每一行有兩個正整數 A,B，代表人民 A 討厭 B。

如果沒有辦法邀請到 K 個人以上來參加，請輸出一行 "NIE"。

否則，第 1 行請你輸出 1 個正整數 W，代表兔王最多可以邀請 W 個人。
第 2 行請接著輸出 W 個正整數，代表邀請這 W 個人是一種合法的選擇。
若存在多組解請輸出隨便一種就可以了。

Sample Input:Sample Output:

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

HINT:

Source:

POI 13 Stage 3

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-ocen	1000ms	131072kb
1	1000ms	131072kb	10
2-ocen	1000ms	131072kb
2	1000ms	131072kb	10
3-ocen	1000ms	131072kb
3	1000ms	131072kb	10
4-ocen	1000ms	131072kb
4	1000ms	131072kb	10
5-ocen	15000ms	131072kb
5-1	1000ms	131072kb	10
5-2	1000ms	131072kb
5-3	1000ms	131072kb
6-1	2000ms	131072kb	10
6-2	13000ms	131072kb
6-3	13000ms	131072kb
7-1	1500ms	131072kb	10
7-2	13000ms	131072kb
7-3	13000ms	131072kb
7-4	13000ms	131072kb
8-1	2000ms	131072kb	10
8-2	13000ms	131072kb
8-3	13000ms	131072kb
8-4	1000ms	131072kb
9-1	1000ms	131072kb	10
9-2	13000ms	131072kb
9-3	13000ms	131072kb
9-4	1000ms	131072kb
10-1	1000ms	131072kb	10
10-2	13000ms	131072kb
10-3	13000ms	131072kb
10-4	1000ms	131072kb