题目描述

小明有一幅$n$个点的无向图，一开始没有边。

一共$m$秒。第$i$秒，一条边$(x_i,y_i)$诞生了。

小明还有$q$个问题，第$i$个问题是，编号在区间$[l_i,r_i]$内的所有点，什么时候连通。

请给小明回答一下这个问题。

输入格式

第一行输入$n,m,q$。

接下来$m$行，输入$x_i,y_i$。

接下来$q$行，输入$l_i,r_i$。

输出格式

对于每组询问，输出一个答案，用空格隔开。

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

3 3 0 5 5

下发文件

数据范围

对于10%的数据：$n,q\leq 400,m\leq 800$。

对于另25%的数据：$q\leq 100$。

对于另20%的数据：保证$r_i-l_i=1$。

对于100%的数据：$1\leq n\leq 10^5,1\leq m,q\leq 2\times 10^5,1\leq x_i,y_i,l_i,r_i\leq n,l_i\leq r_i$。保证图最终连通。