Cereal 2

题目描述

Farmer John 的奶牛们最喜欢的早餐莫过于麦片了！事实上，奶牛们的胃口非常大，每顿饭都会吃掉整整一盒麦片。 农场最近收到了一批包含 $M$ 种不同麦片的货物 $(2\le M\le 10^5)$。不幸的是，每种麦片都只有一盒！每头奶牛共有 $N$ 头 $(1\le N\le 10^5)$，都有一种最喜欢的麦片和一种第二喜欢的麦片。当给奶牛一个可选择的麦片集合时，她会执行如下过程： 如果她最喜欢的麦片盒仍然可用，就拿走并离开。 否则，如果她第二喜欢的麦片盒仍然可用，就拿走并离开。 否则，她会失望地哞哞叫，然后不拿任何麦片就离开。 请在你可以最优地重排列奶牛出场顺序的前提下，求最少有多少头奶牛会挨饿。 同时，找出任意一种能达到该最小值的 $N$ 头奶牛的排列。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M.$ 对于每个 $1\le i\le N,$ 第 $i$ 行包含两个用空格分隔的整数 $f_i$ 和 $s_i$ ($1\le f_i,s_i\le M$ 且 $f_i\neq s_i$)，分别表示第 $i$ 头奶牛最喜欢和第二喜欢的麦片编号。

输出格式

输出最少挨饿的奶牛数量，然后输出任意一个能达到该最小值的 $1\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

提示

在该示例中，有 $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]$ 都不会挨饿。 可以证明，在最后五头奶牛中，至少有一头必须挨饿。 SCORING: 在 $14$ 个测试点中有 $4$ 个满足 $N,M\le 100$。 在 $14$ 个测试点中有 $10$ 个没有额外限制。 Problem credits: Dhruv Rohatgi

标签: USACO|2022|Silver

来源

USACO|2022|Silver