Elearning CodePath – CTP Online Judge

Những con đường thừa

DSU03_REDUNDANT

🟢 Easy #DSU

## Đề bài

Có `N` thành phố được đánh số từ `1` đến `N`. Các con đường hai chiều được xây lần lượt theo thứ tự từ `1` đến `M`.

Một con đường mới được gọi là đường thừa nếu ngay trước khi xây con đường đó, hai thành phố ở hai đầu đường đã có thể đi đến nhau thông qua các con đường đã xây trước đó.

Sau mỗi lần xây đường, hãy in ra tổng số đường thừa đã xuất hiện từ đầu đến hiện tại.

## Dữ liệu vào

- Dòng đầu gồm hai số nguyên `N M`.
- `M` dòng tiếp theo, dòng thứ `i` gồm hai số `u_i v_i`, là con đường được xây ở bước `i`.

## Dữ liệu ra

In `M` dòng. Dòng thứ `i` là số đường thừa sau khi xây xong con đường thứ `i`.

## Ràng buộc

- `1 <= N <= 200000`
- `1 <= M <= 200000`
- `1 <= u_i, v_i <= N`
- `u_i != v_i`
- Có thể có nhiều con đường nối cùng một cặp thành phố.

## Subtask

| Subtask | Điểm | Ràng buộc |
| --- | ---: | --- |
| 1 | 20 | `N, M <= 30` |
| 2 | 30 | `N, M <= 3000` |
| 3 | 50 | Không có ràng buộc bổ sung |

## Ví dụ

### Input

```text
4 5
1 2
2 3
1 3
3 4
1 4
```

### Output

```text
0
0
1
1
2
```

## Giải thích ví dụ

- Đường `(1,2)` và `(2,3)` giúp nối thêm thành phố mới, chưa thừa.
- Trước khi xây `(1,3)`, đã có đường đi `1 - 2 - 3`, nên đây là đường thừa.
- Đường `(3,4)` nối thêm thành phố `4`, chưa thừa.
- Trước khi xây `(1,4)`, `1` và `4` đã liên thông, nên thêm một đường thừa nữa.

✅ Đã AC: 1 / 1 submissions