Elearning CodePath – CTP Online Judge

Sửa chữa điện

2026_DHBB_TI040_B003

🟢 Easy

Mạng cấp điện gồm `N` trạm và `M` đường dây hai chiều, các đường dây được đánh số từ `1` đến `M` theo thứ tự nhập. Trạm `1` là nguồn. Một trạm đang có điện khi tồn tại đường đi từ trạm đó tới trạm `1` qua các đường dây còn hoạt động.

Sau trạng thái ban đầu, lần lượt xảy ra `Q` sự cố. Sự cố thứ `i` làm ngừng vĩnh viễn đường dây có chỉ số được cho ở dòng sự kiện thứ `i`; một đường dây xuất hiện nhiều nhất một lần trong danh sách sự cố.

Với từng trạm `v = 2..N`, hãy xác định thời điểm đầu tiên mà trạm mất kết nối với nguồn. Ghi `0` nếu trạm đã không nối với nguồn trước sự cố thứ nhất, và ghi `-1` nếu trạm vẫn nối với nguồn sau toàn bộ `Q` sự cố.

### Input
- Dòng đầu chứa `N M Q`.
- `M` dòng tiếp theo chứa hai đầu mút của các đường dây, theo thứ tự 1..M.
- `Q` dòng tiếp theo, dòng thứ `i` chứa chỉ số đường dây dừng ở sự kiện `i`. Mỗi đường dây xuất hiện nhiều nhất một lần trong danh sách sự kiện.

### Output
In `N-1` dòng; dòng ứng với trạm `v=2..N` là kết quả của trạm đó.

### Ràng buộc
- `2 <= N <= 200000`.
- `1 <= M <= 300000`.
- `0 <= Q <= M`.

### Subtasks
- S1 - 20 điểm: `N,M,Q <= 200`, mô phỏng sau từng sự kiện.
- S2 - 20 điểm: đồ thị ban đầu là cây.
- S3 - 20 điểm: `Q <= 2000`.
- S4 - 20 điểm: đồ thị ban đầu liên thông.
- S5 - 20 điểm: đầy đủ, xử lý offline bằng DSU đảo thời gian.

### Ví dụ
```text
Input
6 7 4
1 2
2 3
3 4
1 5
5 6
2 5
4 6
6
2
4
7

Output
-1
3
3
3
3
```

✅ Đã AC: 2 / 2 submissions