Không gì khiến những con bò của Nông dân John thích thú hơn ngũ cốc ăn sáng! Thật vậy, chúng háu ăn đến mức mỗi con sẽ ăn hết cả một hộp ngũ cốc trong một bữa.

Gần đây, trang trại nhận được một lô hàng gồm \(M\) loại ngũ cốc khác nhau (\(1 \leq M \leq 10^5\)). Thật không may, mỗi loại ngũ cốc chỉ có đúng một hộp! Mỗi con trong số \(N\) con bò (\(1 \leq N \leq 10^5\)) có một loại ngũ cốc yêu thích nhất và một loại yêu thích thứ hai. Khi được lựa chọn trong số các loại ngũ cốc, một con bò thực hiện quy trình sau:

1. Nếu hộp ngũ cốc yêu thích nhất của nó vẫn còn, nó lấy hộp đó rồi rời đi.
2. Nếu không, nếu hộp ngũ cốc yêu thích thứ hai của nó vẫn còn, nó lấy hộp đó rồi rời đi.
3. Nếu vẫn không được, nó sẽ rống lên vì thất vọng rồi rời đi mà không lấy hộp ngũ cốc nào.

Những con bò đã xếp hàng để nhận ngũ cốc. Với mỗi \(0 \leq i \leq N-1\), hãy xác định có bao nhiêu con bò sẽ lấy được một hộp ngũ cốc nếu Nông dân John loại \(i\) con bò đầu tiên khỏi hàng.

Dữ liệu vào

Tệp cereal.in:

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.

Với mỗi \(1 \leq i \leq N\), dòng thứ \(i\) tiếp theo chứa hai số nguyên \(f_i\) và \(s_i\) cách nhau bởi dấu cách (\(1 \leq f_i,s_i \leq M\) và \(f_i \neq s_i\)), lần lượt biểu thị loại ngũ cốc yêu thích nhất và yêu thích thứ hai của con bò thứ \(i\) trong hàng.

Dữ liệu ra

Tệp cereal.out:

Với mỗi \(0 \leq i \leq N-1\), in một dòng chứa đáp án cho \(i\).

Phân nhóm

• Các test 2–3 thỏa mãn \(N,M \leq 1000\).
• Các test 4–10 không có ràng buộc bổ sung.

Ví dụ

4 2
1 2
1 2
1 2
1 2

2
2
2
1

Nguồn

USACO 2020 US Open Contest, Silver — Cereal

Tác giả bài: Dhruv Rohatgi.