Description

Farmer John’s cows’ favorite breakfast is, of course, cereal. In fact, the cows’ appetites are so large that each cow can eat a whole box of cereal in one meal.

Recently, the farm received a package containing $M$ different types of cereal ($1\le M\le 10^5$). Unfortunately, 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. Given the 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.

The cows line up to take cereal. For each $0\le i\le N-1$, determine how many cows will take a box of cereal if Farmer John removes the first $i$ cows from the line.

Input Format

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$), representing the favorite and second favorite cereals of the $i$-th cow in the line.

Output Format

For each $0\le i\le N-1$, output one line containing the answer for $i$.

4 2
1 2
1 2
1 2
1 2

2
2
2
1

Hint

Sample Explanation

If at least two cows remain, then exactly two cows will take a box of cereal.

Subtasks

• Test cases $2$-$3$ satisfy $N,M\le 10^3$.
• Test cases $4$-$10$ have no additional constraints.

Translated by ChatGPT 5