Optimal Cereal Distribution

Farmer John has N cows and M unique boxes of cereal. Each cow has two preferences: her favorite cereal and her second‐favorite cereal. When a cow enters the barn, she will take her favorite cereal if it is still available; otherwise she will take her second‐favorite cereal if it is available; if neither is available, she leaves hungry. Your task is to determine an ordering of the N cows so that the number of hungry cows is minimized – that is, so that as many cows as possible receive one box of cereal. In addition to reporting the minimum number of hungry cows, you must output any cow ordering that achieves this optimal outcome.

Formally, given N cows (1 ≤ N ≤ 10⁵) and M cereal types (2 ≤ M ≤ 10⁵), where each cereal type appears exactly once and each cow has a pair of distinct cereal preferences (first and second), determine an ordering of the cows such that if the cows select cereal in that order, each cow takes her favorite cereal if it is available, otherwise her second‐favorite if available, otherwise she gets nothing. Output the minimum number of cows that end up hungry (i.e. get no cereal) and one valid ordering that achieves that.

Note that if a cow is served her second choice, it must be because some other cow who prefers that cow’s first choice has already taken it – so the ordering must ensure that for every cow receiving her second choice, the cow who takes her first choice comes earlier.

All formulas should be rendered in LaTeX. For example, \(M\) and \(N\) denote the number of cereal types and cows respectively, and preferences are given as \(\text{first}, \text{second}\).

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

Each of the following \(N\) lines contains two integers representing a cow's favorite cereal and its second‐favorite cereal. Cereal types are numbered from \(1\) to \(M\).

outputFormat

On the first line, output a single integer representing the minimum number of cows that will go hungry.

On the second line, output a permutation of \(N\) integers (separated by spaces) representing the cow ordering that achieves this optimal result. The cows are numbered from \(1\) to \(N\) in the order given in the input.

sample

3 3
1 2
1 3
2 3

0
1 3 2