Elearning CodePath – CTP Online Judge

Cùng đội hay khác đội

DSU04_PARITY

🟢 Easy #DSU

## Đề bài

Có `N` học sinh được đánh số từ `1` đến `N`. Mỗi học sinh thuộc một trong hai đội, nhưng ta chưa biết đội cụ thể của từng người.

Có `Q` phát biểu được đưa ra lần lượt. Phát biểu thứ `i` có dạng:

```text
u v c
```

Trong đó:

- Nếu `c = 0`, phát biểu nói rằng `u` và `v` thuộc cùng đội.
- Nếu `c = 1`, phát biểu nói rằng `u` và `v` thuộc khác đội.

Một phát biểu bị mâu thuẫn nếu không thể gán đội cho các học sinh sao cho tất cả các phát biểu từ đầu đến phát biểu đó cùng đúng.

Hãy tìm chỉ số phát biểu mâu thuẫn đầu tiên. Nếu không có mâu thuẫn, in `0`.

## Dữ liệu vào

- Dòng đầu gồm hai số nguyên `N Q`.
- `Q` dòng tiếp theo, mỗi dòng gồm ba số nguyên `u v c`.

## Dữ liệu ra

In ra một số nguyên duy nhất:

- Chỉ số phát biểu mâu thuẫn đầu tiên.
- Hoặc `0` nếu tất cả phát biểu đều nhất quán.

## Ràng buộc

- `1 <= N <= 200000`
- `1 <= Q <= 200000`
- `1 <= u, v <= N`
- `c` thuộc `{0, 1}`

## Subtask

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

## Ví dụ

### Input

```text
4 4
1 2 1
2 3 1
1 3 1
3 4 0
```

### Output

```text
3
```

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

Từ hai phát biểu đầu:

- `1` khác `2`.
- `2` khác `3`.

Suy ra `1` và `3` phải cùng đội. Nhưng phát biểu thứ `3` lại nói `1` khác `3`, nên phát biểu thứ `3` là mâu thuẫn đầu tiên.

✅ Đã AC: 1 / 2 submissions