P6282 [USACO20OPEN] Cereal S

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.

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.

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

### 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