#2840. ROADBUILD - Xây dựng đường

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

n thành phố và ban đầu không có con đường nào. Nhiệm vụ của bạn là xử lý m yêu cầu xây dựng đường. Với mỗi yêu cầu, hai thành phố a b được cho. Sau khi xây dựng con đường giữa chúng, bạn cần báo cáo số lượng thành phần liên thông của các thành phố.

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên n m : số thành phố và số con đường mới.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên a b mô tả một con đường mới.

Kết quả: Sau mỗi con đường được xây, in ra số lượng thành phần liên thông.

Ví dụ:

Dữ liệu:

5 3
1 2
1 3
4 5

Kết quả:

4
3
2

Giới hạn:

  • 1 \le n \le 10^5
  • 1 \le m \le 2 \cdot 10^5
  • 1 \le a, b \le n