暂无测试数据。

蒜头君是一名商场经理，管理着一家大型的商场。商场里有 $n$ 个不同的商品，每个商品都有一个独特的编号 $1,2,\cdots,n$。

然而，有 $m$ 对商品之间存在互斥关系，例如同一品牌的不同型号的电器，或者不同口味的零食等。为了让顾客在购物时避免购买冗余或者不相关的商品，你需要回答他们 $q$ 次询问。

每个询问都包含 $k$ 个区间 $[l_1,r_1], [l_2,r_2],\cdots,[l_k,r_k]$，表示顾客选择的商品编号必须在这 $k$ 个区间的并集中。你需要判断这 $k$ 个区间的并集中是否存在互斥的商品？

• 如果存在，那么顾客不能同时购买这些商品，你需要回答 1；
• 否则，顾客可以购买这些商品，你需要回答 0。

输入格式

第一行一个整数 $T$ 和一个标识符 $f$，表示数据组数和该测试点是否在线（$1$ 表示在线，$0$ 表示离线）。

对于每组数据：

第一行三个整数 $n, m, q$，含义如题所示。

接下来 $m$ 行，每行两个不同的整数 $x, y$，表示编号 $x$ 和编号 $y$ 的商品之间存在互斥关系。

接下来 $q$ 行，每行第一个整数为 $k$，然后 $2\times k$ 个整数，依次为 $l_1, r_1, l_2, r_2, \cdots , l_k, r_k$，表示每次询问的区间。

输出格式

输出共 $T$ 行，每组数据占一行，为 $q$ 个字符，依次为每个询问的答案。

若一个询问没有包含互斥关系，则答案为 0；否则答案为 1。

数据范围与约定

您可以点击“只看题面”以获得更好的阅读体验。

测试点编号	$0\leq n\leq$	$0\leq m\leq$	$0\leq q\leq$	$0\leq \sum k\leq$
1-2	$2000$	$2000$	$2000$	$2000$
3-4	$10^5$	$2000$	$2000$	$2000$
5-6	$10^5$	$10^5$	$4000$	$4000$
7-8	$10^5$	$10^5$	$20000$	$10^5$
9-10	$10^5$	$10^5$	$10^5$	$10^5$

以上为一组数据的范围 ，保证 $1\leq T \leq 5$ 。

为了便于编写程序，保证 $k$ 个区间互不相交且以左端点递增的顺序给出。

对于 $f=1$ 的 $8$ 、$10$ 号测试点（其余测试点 $f$ 均为 $0$ ） ，每个询问的 $2\times k$ 个区间端点需要异或上 $p$ ， $p$ 表示此前有多少个询问的输出是 $1$ ，处理完一组数据后无需将 $p$ 置 $0$ 。

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

101
10

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

101
10