题目描述

给你 $n$ 个布尔变量和 $m$ 个限制，设 $s_i$ 为 $i$ 的取值。第 $i$ 个限制形如 $s_{u_i}$ 为 $x_i$ 则 $s_{v_i}$ 必须为 $y_i$，同时如果 $s_{v_i}$ 为 $y_i$ 则 $s_{u_i}$ 必须取 $x_i$。
一共 $q$ 次询问，每次询问给出一个区间 $l,r$。求最少把 $l,r$ 划分成多少段连续的区间，使得每段里的限制都可以得到一组合法解。如果无论如何都无法得到合法解，输出 -1。

输入格式

第一行三个数，$n,m,q$。
接下来 $m$ 行每行四个数，代表 $u_i,x_i,v_i,y_i$。
接下来 $q$ 行每行两个数，代表 $l_i,r_i$。

输出格式

对于每个询问输出一个数作为答案，如果无法得到答案输出 -1。

3 4 2
1 0 2 0
1 1 3 0
3 0 2 0
1 1 2 1
1 3
3 4

2
1

4 5 3
1 1 2 1
2 0 3 0
4 1 1 0
2 1 4 0
4 0 3 0
1 4
2 5
3 5

1
2
1

提示

样例解释一
对于第一个询问，可以分成 $[1,2]$ 和 $3$ 两段。
对于第二个询问，分成 $[3,4]$ 一段。

样例解释二
对于第一个询问，分成 $[1,4]$ 一段。
对于第二个询问，可以分成 $[2,3]$ 和 $[4,5]$ 两段。
对于第三个询问，分成 $[3,5]$ 一段。

对于 $100\%$ 的数据，$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\}$