Luật Chơi Sinh Tử
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Có N người chơi trong trò chơi sinh tử. Có M quy tắc, mỗi quy tắc có dạng: "Nếu người i sống, thì người j phải sống" hoặc "Nếu người i chết, thì người j phải chết" hoặc "Ít nhất một trong hai người i, j phải sống" hoặc "Ít nhất một trong hai người i, j phải chết".
Cụ thể, mỗi quy tắc được cho dưới dạng:
- Loại 1:
1 i j— ít nhất một trong hai người i, j phải sống (xi ∨ xj) - Loại 2:
2 i j— ít nhất một trong hai người i, j phải chết (¬xi ∨ ¬xj) - Loại 3:
3 i j— nếu i sống thì j phải sống (xi → xj, tương đương ¬xi ∨ xj) - Loại 4:
4 i j— đúng một trong hai người sống (xi ⊕ xj)
Hãy xác định xem có tồn tại cách phân chia sống/chết cho N người thỏa mãn tất cả M quy tắc hay không.
Nếu có, in "YES" và dòng tiếp theo in N số, số thứ i là 1 nếu người i sống, 0 nếu chết. Nếu không, in "NO".
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
- M dòng tiếp theo: t i j (1 ≤ t ≤ 4, 1 ≤ i, j ≤ N)
Dữ liệu ra
- "YES" hoặc "NO", nếu YES thì dòng tiếp theo in phương án.
Ví dụ
| Input | Output |
|---|---|
| 3 3\n1 1 2\n2 2 3\n3 1 3 | YES\n1 0 1 |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
Community Discussion