Problem Description

Farmer John’s cows, of course, love cereal for breakfast. In fact, their appetites are so big that each cow can eat an entire box of cereal in one meal.

Recently, the farm received a package containing $M$ different kinds of cereal ($2\le M\le 10^5$). Unfortunately, there is only one box of each kind of cereal. Each of the $N$ cows ($1\le N\le 10^5$) has a favorite cereal and a second favorite cereal. Given some available cereals, a cow will follow this process:

• If her favorite cereal is still available, she takes it and leaves.

• Otherwise, if her second favorite cereal is still available, she takes it and leaves.

• Otherwise, she moos in disappointment and leaves without taking any cereal.

When you arrange these cows in the best possible order, find the minimum number of hungry cows. Also, output any ordering of the $N$ cows that can achieve this minimum.

Input Format

The first line contains two space-separated integers $N$ and $M$.

For each $1\le i\le N$, line $i$ contains two space-separated integers $f_i$ and $s_i$ ($1\le f_i,s_i\le M$, and $f_i\neq s_i$), the favorite and second favorite cereal of cow $i$.

Output Format

Output the minimum number of hungry cows, and output any permutation of $1\ldots N$ that can achieve this minimum. If there are multiple valid permutations, output any one of them.

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

Hint

【Sample Explanation】

In this example, there are $8$ cows and $10$ kinds of cereal.

Note that we solve the first three cows independently from the last five cows, because they do not like any cereal in common.

If the first three cows choose in the order $[1,2,3]$, then cow $1$ will choose cereal $2$, cow $2$ will choose cereal $3$, and cow $3$ will be hungry.

If the first three cows choose in the order $[1,3,2]$, then cow $1$ will choose cereal $2$, cow $3$ will choose cereal $3$, and cow $2$ will choose cereal $4$; no cow will be hungry.

Of course, there are other orderings that make all three of the first cows not hungry. For example, if the first three cows choose in the order $[3,1,2]$, then cow $3$ will choose cereal $2$, cow $1$ will choose cereal $1$, and cow $2$ will choose cereal $3$; similarly, cows $[1,2,3]$ will all not be hungry.

It can be proven that among the last five cows, at least one cow will be hungry.

【Constraints】

• Among the $14$ test points, $4$ test points satisfy $N,M\le 100$.

• Among the $14$ test points, the remaining $10$ test points have no additional constraints.

【Notes】

This problem uses a self-written Special Judge. If you have questions about this or want to hack, please message the author privately or make a post.

Translated by ChatGPT 5