Thỏa mãn biểu thức 2-SAT
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 (0hoặc1) 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$
Community Discussion