O. 2-SAT с закреплёнными

То же, что классная задача O, но часть переменных заранее закреплена: сказано, что $x_i$ обязана быть равна $e$. Определите, существует ли набор значений, удовлетворяющий и утверждениям, и закреплениям.

Ничего нового не требуется. Закрепление $x_i = e$ — это утверждение $(x_i = e) \lor (x_i = e)$: единственный способ сделать его истинным — присвоить $x_i$ значение $e$. Добавьте такие утверждения к остальным и решайте ту же задачу.

Что при этом происходит в графе импликаций: появляется ребро из литерала $x_i = 1 - e$ в литерал $x_i = e$. Если из $x_i = e$ и без того был путь в $x_i = 1 - e$, оба литерала окажутся в одной компоненте, и ответ станет отрицательным — ровно как и требуется.

Противоречивые закрепления, где одна и та же переменная закреплена и в ноль, и в единицу, тоже обрабатываются сами собой.

Первая строка содержит числа $n$ ($1 \le n \le 10^5$), $m$ ($0 \le m \le 3 \cdot 10^5$) и $k$ ($0 \le k \le 10^5$).

Далее идут $m$ строк по четыре числа $i_1$, $e_1$, $i_2$, $e_2$ — утверждения, затем $k$ строк по два числа $i$, $e$ — закрепления. Везде $0 \le i, i_j < n$ и $0 \le e, e_j \le 1$.

Одно слово: YES или NO.