Luật Chơi Sinh Tử

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved