Cereals for Cows

Farmer John's cows love cereal for breakfast! There are \(M\) different types of cereal boxes, each available in exactly one box, and \(N\) cows in line. Each cow has a favorite cereal and a second favorite cereal. The cows follow this process in order:

• If her favorite cereal is still available, she takes it and leaves.
• Otherwise, if her second favorite cereal is available, she takes that one and leaves.
• If neither is available, she leaves disappointed.

For each \(0 \le i \le N-1\), if Farmer John removes the first \(i\) cows from the line, determine how many cows end up taking a box of cereal.

Note: The cows remaining in line still receive cereal in their original order.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le N, M \le 10^5\)) -- the number of cows and the number of cereal types respectively.

The following \(N\) lines each contain two integers \(a\) and \(b\) (each between \(1\) and \(M\)), where \(a\) is the favorite cereal and \(b\) is the second favorite cereal of a cow. The cows are given in the order they stand in line (from the front to the back).

When processing the answer, consider queries for each \(i\) from \(0\) to \(N-1\): if the first \(i\) cows are removed from the line, the remaining cows take cereal following the rules described above.

outputFormat

Output \(N\) lines. The \(i\)-th line (0-indexed) should contain a single integer representing the number of cows that take a box of cereal when the first \(i\) cows are removed.

sample

3 4
1 2
1 3
2 4

3
2
1