E. Qpwoeirut and Vertices

给定一张 $n$ 个点 $m$ 条边的无向连通图，有 $q$ 个询问，每次询问给定两个数 $l,r$，请你给出最小的 $k$ 使得：

仅使用前 $k$ 条边就能使所有点对 $(a,b)$ 联通，其中 $a,b$ 满足 $l \leq a \leq b \leq r$。

$n \leq 10^5,m,q \leq 2\times 10^5$

做了 NOI2018 归程 学到的东西。