题目详情题解（0）讨论（0）提交记录（0）

AT_agc002_d.[AGC002D] Stamp Rally

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一张 nn 个点，mm 条边的无向图，点的编号从 11 到 nn，边的编号从 11 到 mm，第 ii 条边连接定点 aia_i 和 bib_i。保证图联通。

在这张图上，有 QQ 次询问，每次询问中有一对兄弟进行如下操作：

  • 最开始的时候哥哥在 xix_i 点，弟弟在 yiy_i 点，兄弟两人可以通过边从一个点走到另一个点。

  • 兄弟俩需要总计访问恰好 ziz_i 个顶点。不过哥哥弟弟都访问的顶点只能算一个。

  • 其中兄弟俩经过的边的编号最大值为代价。兄弟俩希望最小化代价。

求每组兄弟的代价。

输入格式

第一行包含两个正整数 NN 和 MM。

接下来 MM 行，每行包含两个正整数 ai,bia_i, b_i，表示 aia_i 和 bib_i 之间有一条无向边。

接下来一行包含一个正整数 QQ。

接下来 QQ 行，每行包含三个整数 xi,yi,zix_i, y_i, z_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

说明/提示

由 yangyang1000 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页