当前没有测试数据。

题目描述

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

最近农场收到了一份快递，内有 $M$ 种不同种类的麦片。不幸的是，每种麦片只有一箱！$N$ 头奶牛中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：

1. 如果她最爱的麦片还在，取走并离开。
2. 否则，如果她第二喜爱的麦片还在，取走并离开。
3. 否则，她会失望地哞叫一声然后不带走一片麦片地离开。

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

• $2\le M\le 10^5$
• $1\le N\le 10^5$

输入格式

输入的第一行包含两个空格分隔的整数 $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

8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8

测试点性质

• $14$ 个测试点中的 $4$ 个测试点满足 $N,M\le 100$。
• $14$ 个测试点中的 $4$ 个测试点没有额外限制。

题目提供者

供题：Dhruv Rohatgi