P7843 "C.E.L.U-03" Boolean.

You are given $n$ Boolean variables and $m$ constraints. Let $s_i$ be the value of variable $i$. The $i$-th constraint is of the form: if $s_{u_i}$ is $x_i$, then $s_{v_i}$ must be $y_i$; at the same time, if $s_{v_i}$ is $y_i$, then $s_{u_i}$ must be $x_i$. There are $q$ queries in total. Each query gives an interval $l,r$. Find the minimum number of continuous segments to partition $[l,r]$ into, such that the constraints within each segment have at least one legal solution. If no legal solution can be obtained no matter what, output `-1`.

The first line contains three integers $n,m,q$. The next $m$ lines each contain four integers, representing $u_i,x_i,v_i,y_i$. The next $q$ lines each contain two integers, representing $l_i,r_i$.

For each query, output one integer as the answer. If it is impossible to get an answer, output `-1`.

**Sample Explanation 1** For the first query, it can be split into two segments: $[1,2]$ and $3$. For the second query, it is one segment: $[3,4]$. **Sample Explanation 2** For the first query, it is one segment: $[1,4]$. For the second query, it can be split into two segments: $[2,3]$ and $[4,5]$. For the third query, it is one segment: $[3,5]$. | Data ID | $n\leq$ | $m\leq$ | $q\leq$ | |:---:|:---:|:---:|:---:| | $1$ | $30$ | $100$ | $300$ | | $2\sim 4$ | $300$ | $10^3$ | $10^3$ | | $5\sim 7$ | $10^4$ | $5\times10^4$ | $10^6$ | | $8\sim 10$ | $10^5$ | $6\times10^5$ | $10^6$ | For $100\%$ of the testdata, $1\le n\le10^5,1\le m\le6\times10^5,1\le q\le10^6,1\le u,v\le n,1\le l\le r\le m,x,y\in \{0,1\}$. Translated by ChatGPT 5