#535. 「多校联考 2022 Round 4」遗产

内存限制:512 MiB 时间限制:3000 ms 输入文件:legacy.in 输出文件:legacy.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 C 所生活的土地——提塔尔耶拉,是一片神代文明与现代文明交融的土地,神代神明留下的遗迹里埋藏着诸多珍贵的遗产。现代人探索神代遗迹,通过研究遗迹中的遗物使得文明获得了飞速的发展。提塔尔耶拉可以抽象成 个点, 条边的无向图,第 条边连接城市 ,长度为

小 C 的职业是探索者,以发掘遗迹为生,显然,在一定的时间内访问的城市越多,可能得到的利润就越多。

小 C 的搭档小 D 因为执行任务,目前跟小 C 分居在不同的城市。在接下来的 天里,小 C 和小 D 会分别位于城市 ,她们想知道如果她们二人在第 天一共要访问 不同的城市(她们初始所在的城市也认为是访问过的城市),所经过的边的长度的最大值是多少。

你作为她们的朋友兼 OIer,需要解决这个问题。

输入格式

从文件 中读入数据。

第一行两个正整数

接下来 行,每行三个正整数

接下来一行一个正整数

接下来 行,每行三个正整数

输出格式

输出到文件 中。

输出 行,每行一个正整数表示答案。

样例

样例 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

样例 2

见选手目录下的

该样例满足测试点 的数据范围。

样例 3

见选手目录下的

该样例满足测试点 的数据范围。

样例 4

见选手目录下的

该样例满足测试点 的数据范围。

数据范围与提示

数据范围

对于所有测试点:,保证给定的图连通,且无自环,无重边。

每个测试点的具体限制见下表:

测试点编号 特殊限制