Thỏa mãn biểu thức 2-SAT

Buổi 78 — Bế giảng Graphs
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho $N$ biến boolean $x_1, x_2, \dots, x_N$ và $M$ mệnh đề dạng $(a \lor b)$. Trong mỗi mệnh đề, một biến hoặc phủ định của nó được biểu diễn bởi một số nguyên khác $0$ thuộc $[-N, N]$: số dương $v$ đại diện cho $x_v$, còn số âm $-v$ đại diện cho $\neg x_v$.

Hãy kiểm tra xem có tồn tại một cách gán giá trị 0 (sai) hoặc 1 (đúng) cho $N$ biến sao cho tất cả $M$ mệnh đề đều đúng hay không. Nếu có, hãy in ra YES và một nghiệm hợp lệ. Nếu không, in ra NO.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, 1 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a, b$ ($1 \le |a|, |b| \le N$).
Dữ liệu ra
  • Nếu không có nghiệm, in ra NO.
  • Nếu có nghiệm, dòng đầu tiên in YES, dòng thứ hai in $N$ số nguyên (0 hoặc 1) cách nhau bởi dấu cách, tương ứng với giá trị của $x_1, x_2, \dots, x_N$.
Ví dụ
Input Output
2 3
1 2
-1 2
1 -2
YES
1 1
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le M \le 2 \cdot 10^5$
Draft saved