问题陈述
我们有一个无向图 N 顶点和 M 边缘。顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。边缘 i 连接顶点 a_i 和 b_i。该图已连接。
在此图表中, Q 一对兄弟正在参加一项名为“ 集邮活动。集邮活动 i第对如下:
- 一哥从顶点开始 x_i,另一个从顶点开始 y_i.
- 两人沿着图的边缘探索去参观 z_i 顶点总数,包括起始顶点。在这里,一个顶点仅被计数一次,即使它被访问多次,或者被两个兄弟访问过。
- 分数定义为它们中的任何一个遍历的边的最大索引。他们的目标是最小化这个值。
找出每对的最低可能分数。
约束
- 3≤N≤10^5
- N−1≤M≤10^5
- 1≤a_i<b_i≤N
- 给定的图形已连接。
- 1≤Q≤10^5
- 1≤x_j<y_j≤N
- 3≤z_j≤N
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 : a_M b_M Q x_1 y_1 z_1 x_2 y_2 z_2 : x_Q y_Q z_Q
输出
打印 Q 行。的 i- 第行应包含该项目的最低可能分数 i第一对兄弟。
示例输入 1
5 6 2 3 4 5 1 2 1 3 1 4 1 5 6 2 4 3 2 4 4 2 4 5 1 3 3 1 3 4 1 3 5
示例输出 1
1 2 3 1 5 5