P5378: 谷物2
传统题
1.000s
时间限制
256MB
内存限制
2 提交
0 解决
【题目描述】
Farmer John 的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。
最近农场收到了一份快递，内有 M 种不同种类的麦片（2≤M≤10
5）。不幸的是，每种麦片只有一箱！N 头奶牛（1≤N≤10
5）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：
1. 如果她最爱的麦片还在，取走并离开。
2. 否则，如果她第二喜爱的麦片还在，取走并离开。
3. 否则，她会失望地哞叫一声然后不带走一片麦片地离开。
当你最优地排列这些奶牛时，求饥饿的奶牛的最小数量。同时，求出任意一个可以达到此最小值的N头奶牛的排列。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含两个空格分隔的整数N和M。
对于每一个1≤i≤N，
第i行包含两个空格分隔的整数fi和si（1≤fi,si≤M，且 fi≠si
），为第i头奶牛最喜爱和第二喜爱的麦片。
输出格式（输出至终端 / 标准输出）：
输出饥饿的奶牛的最小数量，并输出任意一个可以达到此最小值的1…N 的排列。如果有多个符合要求的排列，输出任意一个。
输入样例：
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
输出样例：
1
1
3
2
8
4
6
5
7
在这个例子中，有8头奶牛和10种麦片。
注意我们对前三头奶牛独立于后五头奶牛求解，因为她们没有共同喜欢的麦片。
如果前三头奶牛按顺序[1,2,3]进行选择，则奶牛1会选择麦片2
，奶牛2会选择麦片3
，奶牛3会饥饿。
如果前三头奶牛按顺序[1,3,2]进行选择，则奶牛1会选择麦片2
，奶牛3会选择麦片3
，奶牛2会选择麦片4；没有奶牛会饥饿。
当然，还存在其他排列使得前三头奶牛均不饥饿。例如，如果前三头奶牛按顺序[3,1,2]选择，则奶牛3会选择麦片2
，奶牛1会选择麦片1
，奶牛2会选择麦片3
；同样，奶牛[1,2,3]均不会饥饿。
可以证明在后五头奶牛中，至少一头会饥饿。
测试点性质：
14个测试点中的4个测试点满足 N,M≤100。
14个测试点中的4个测试点没有额外限制。