← 返回题目列表

AtCoder · agc002_d

D. 集邮活动

中文机器翻译题面 查看原题

问题陈述

我们有一个无向图 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