#USACOC2223C. Cereal 2
Cereal 2
No testdata at current.
题目描述
Farmer John 的奶牛们的早餐最爱当然是麦片了!事实上,奶牛们的胃口是如此之大,每头奶牛一顿饭可以吃掉整整一箱麦片。
最近农场收到了一份快递,内有 种不同种类的麦片。不幸的是,每种麦片只有一箱! 头奶牛中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片,奶牛会执行如下的过程:
- 如果她最爱的麦片还在,取走并离开。
- 否则,如果她第二喜爱的麦片还在,取走并离开。
- 否则,她会失望地哞叫一声然后不带走一片麦片地离开。
当你最优地排列这些奶牛时,求饥饿的奶牛的最小数量。同时,求出任意一个可以达到此最小值的 头奶牛的排列。
输入格式
输入的第一行包含两个空格分隔的整数 和 。
对于每一个 ,第 行包含两个空格分隔的整数 和 (,且 ),为第 头奶牛最喜爱和第二喜爱的麦片。
输出格式
输出饥饿的奶牛的最小数量,并输出任意一个可以达到此最小值的 的排列。如果有多个符合要求的排列,输出任意一个。
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
测试点性质
- 个测试点中的 个测试点满足 。
- 个测试点中的 个测试点没有额外限制。
题目提供者
供题:Dhruv Rohatgi