Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/onbridge

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:

1
5 10
3 0
0 2
1 0
1 3
1 4
2 4
4 0
2 1
2 3
3 4

Kết quả đúng là:

1
2
3
1
2
0
0
0
0
0