Cereal 2

Farmer John's cows like cereal for breakfast more than anything else. Their appetites are so large that each cow eats an entire box of cereal in one meal.

The farm has just received a shipment of $M$ types of cereal $(2\le M\le 10^5)$. There is only one box of each type. Each of the $N$ cows $(1\le N\le 10^5)$ has a favorite cereal and a second-favorite cereal. When a cow gets a chance to choose cereal, she does the following:

1. If the box of her favorite cereal is still available, she takes it and leaves.
2. Otherwise, if the box of her second-favorite cereal is still available, she takes it and leaves.
3. Otherwise, she moos with disappointment and leaves without taking any cereal.

Find the minimum number of cows that go hungry when the cows are ordered optimally. Also find any permutation of the $N$ cows that achieves this minimum.

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

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

Print the minimum number of cows that go hungry, followed by any permutation of $1\ldots N$ that achieves this minimum. If several permutations achieve the minimum, any one of them is accepted.

In this case, there are $8$ cows and $10$ types of cereal.

The first three cows can be solved independently of the last five because they share no favorite cereal.

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

If the first three cows choose in the order [1,3,2], then cow $1$ chooses cereal $2$, cow $3$ chooses cereal $3$, and cow $2$ chooses cereal $4$; none of these cows goes hungry.

There are other permutations in which none of the first three cows goes hungry. For example, if they choose in the order [3,1,2], then cow $3$ chooses cereal $2$, cow $1$ chooses cereal $1$, and cow $2$ chooses cereal $3$; again, none of cows [1,2,3] goes hungry.

One can show that at least one of the last five cows must go hungry.