Elearning CodePath – CTP Online Judge

Kích thước thành phần

DSU02_SIZE

## Đề bài

Có `N` đỉnh được đánh số từ `1` đến `N`. Ban đầu mỗi đỉnh là một thành phần riêng biệt.

Bạn cần xử lý `Q` thao tác:

- `1 u v`: gộp thành phần chứa `u` và thành phần chứa `v`.
- `2 u`: hỏi kích thước thành phần hiện tại chứa `u`.
- `3`: hỏi kích thước lớn nhất trong tất cả các thành phần hiện tại.

## Dữ liệu vào

- Dòng đầu gồm hai số nguyên `N Q`.
- `Q` dòng tiếp theo mô tả các thao tác theo một trong ba dạng trên.

## Dữ liệu ra

Với mỗi thao tác loại `2` hoặc loại `3`, in ra một số nguyên là đáp án.

## Ràng buộc

- `1 <= N <= 200000`
- `1 <= Q <= 200000`
- `1 <= u, v <= N`
- Có ít nhất một thao tác loại `2` hoặc `3`.

## Subtask

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

## Ví dụ

### Input

```text
6 8
3
1 1 2
2 1
1 3 4
1 2 3
2 4
3
2 6
```

### Output

```text
1
2
4
4
1
```

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

Ban đầu thành phần lớn nhất có kích thước `1`.

Sau khi gộp `(1,2)`, thành phần chứa `1` có kích thước `2`.

Sau khi gộp thêm `(3,4)` và `(2,3)`, các đỉnh `1,2,3,4` cùng một thành phần kích thước `4`.

✅ Đã AC: 1 / 1 submissions