#P3094. [USACO22JAN] Cereal 2 S

[USACO22JAN] Cereal 2 S

题目描述

Farmer John 的奶牛们的早餐最爱当然是麦片了!事实上,奶牛们的胃口是如此之大,每头奶牛一顿饭可以吃掉整整一箱麦片。

最近农场收到了一份快递,内有 MM 种不同种类的麦片(2M1052\le M\le 10^5)。不幸的是,每种麦片只有一箱!NN 头奶牛(1N1051\le N\le 10^5)中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片,奶牛会执行如下的过程:

  • 如果她最爱的麦片还在,取走并离开。

  • 否则,如果她第二喜爱的麦片还在,取走并离开。

  • 否则,她会失望地哞叫一声然后不带走一片麦片地离开。

当你最优地排列这些奶牛时,求饥饿的奶牛的最小数量。同时,求出任意一个可以达到此最小值的 NN 头奶牛的排列。

输入格式

输入的第一行包含两个空格分隔的整数 NNMM

对于每一个 1iN1\le i\le N,第 ii 行包含两个空格分隔的整数 fif_isis_i1fi,siM1\le f_i,s_i\le M,且 fisif_i\neq s_i),为第 ii 头奶牛最喜爱和第二喜爱的麦片。

输出格式

输出饥饿的奶牛的最小数量,并输出任意一个可以达到此最小值的 1N1\ldots 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

提示

【样例解释】

在这个例子中,有 88 头奶牛和 1010 种麦片。

注意我们对前三头奶牛独立于后五头奶牛求解,因为她们没有共同喜欢的麦片。

如果前三头奶牛按顺序 [1,2,3][1,2,3] 进行选择,则奶牛 11 会选择麦片 22,奶牛 22 会选择麦片 33,奶牛 33 会饥饿。

如果前三头奶牛按顺序 [1,3,2][1,3,2] 进行选择,则奶牛 11 会选择麦片 22,奶牛 33 会选择麦片 33,奶牛 22 会选择麦片 44;没有奶牛会饥饿。

当然,还存在其他排列使得前三头奶牛均不饥饿。例如,如果前三头奶牛按顺序 [3,1,2][3,1,2] 选择,则奶牛 33 会选择麦片 22,奶牛 11 会选择麦片 11,奶牛 22 会选择麦片 33;同样,奶牛 [1,2,3][1,2,3] 均不会饥饿。

可以证明在后五头奶牛中,至少一头会饥饿。

【数据范围】

  • 1414 个测试点中的 44 个测试点满足 N,M100N,M\le 100

  • 1414 个测试点中的 1010 个测试点没有额外限制。

【说明】

本题采用自行编写的 Special Judge。如果对此有疑问或想要 hack,请私信编写者发帖