ONBRIDGE - VNOI

ONBRIDGE - Online Bridge Searching

Giới hạn

Thời gian: 0.14s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một đồ thị N đỉnh, đánh số từ 0 đến N - 1. Ban đầu đồ thị không có cạnh nào. Lần lượt thêm vào đồ thị M cạnh vô hướng (u, v) với (0 <= u, v <= N - 1). Sau mỗi lần thêm 1 cạnh, in ra số lượng cầu hiện có trong đồ thị. Dữ liệu đảm bảo không có yêu cầu thêm vào 1 cạnh đã tồn tại, hoặc 1 cạnh nối 1 đỉnh với chính nó.

Input

Dòng đầu ghi số nguyên T (T <= 10) là số lượng bộ test. Mỗi bộ test bắt đầu bằng 2 số nguyên N (1 <= N <= 50000) và M (1 <= M <= 100000), theo sau là M dòng, mỗi dòng ghi 1 cặp số nguyên (u, v) thể hiện một yêu cầu thêm vào cạnh (u, v).

Output

Sau mỗi yêu cầu thêm cạnh, in ra 1 số nguyên trên 1 dòng là số lượng cầu hiện có trong đồ thị.

Example

Với dữ liệu:

Kết quả đúng là:

Người up: racer