#D. [AGC002D] Stamp Rally

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

第一行两个正整数，代表 $N$ 和 $M$ 。

接下来 $M$ 行，第 $i$ 行有两个正整数 $a_{i}, b_{i}$ ，代表 $a_{i}$ 和 $b_{i}$ 之间有一条无向边。

接下来一行有一个正整数，代表 $Q$ 。

接下来 $Q$ 行，第 $i$ 行有三个整数 $x_{i}, y_{i}, z_{i}$ ，表示一种询问。

对于每个询问，输出一行一个整数表示答案。

一张连通图， $q$ 次询问从两个点 $x$ 和 $y$ 出发，希望经过的点数量等于 $z$ （每个点可以重复经过，但是重复经过只计算一次），求经过的边最大编号最小是多少。

对于 $100%$ 的数据， $3 \leq N \leq 1 0^{5}$ ， $N - 1 \leq 1 0^{5}$ ， $1 \leq Q \leq 1 0^{5}$ ，其它数据保证合法。

1
2
3
1
5
5</p>

</p>