Farmer John's cows are very fond of cereal for breakfast. And they eat a box of cereal at a time.
The farm has recently received M (1≤M≤10
5) different types of flakes. Unfortunately, there is exactly one box of each type of cereal. Each of the N cows (1≤N≤10
5) has a favorite cereal type and a second favorite cereal type. The process of choosing flakes by cows is as follows:
- If a crate of her favorite cereal is still available, the cow takes it and leaves.
- Otherwise, if the crate of her second favorite cereal is still available, the cow takes it and leaves.
- Otherwise, she leaves with empty hooves
Cows lined up for cereal. For each of 0≤i≤N−1 cows, determine how many cows will take the cereal box if the FD removes the first i cows from the queue.
Input
The first line contains two space-separated integers N and M.
For every 1 ≤ i≤ N, i-th line contains two space-separated integers f
i and s
i (1 ≤ f
i,s
i ;≤ M and f
i ≠ s
i) denoting the i-th cow's favorite and second favorite flakes in the queue.
Imprint
For every 0 ≤ i≤ N−1, print a line containing the answer for i.
Examples
| # |
Input |
Output |
| 1 |
4 2
1 2
1 2
1 2
1 2
| 2
2
2
1 |