#F7. 城市生长
城市生长
T3 城市生长(rebuild)
时间限制:2.0 秒 空间限制:256 MB
题目描述
有 座城市,编号为 。起初城市之间没有任何道路。接下来有 条道路会依次建成,第 条道路连接城市 和 ,建成时间为 。道路是双向的,建成后可以立即通行。可能存在重边,但不会出现自环。
城市之间的连通性会随时间变化。现在有 次询问,第 次询问给出城市 和整数 :
求最早的日期 ,使得在日期 结束时(即所有满足 的道路都建成后),城市 所在的连通块中至少有 座城市。
如果不存在这样的日期,输出 。特别地,当 时答案为 (不需要任何道路,城市 自己就构成一个大小为 的连通块)。
输入格式
第一行三个正整数 。
接下来 行,每行三个正整数 ,表示一条连接 和 、建成时间为 的道路。
接下来 行,每行两个正整数 ,表示一次询问。
输出格式
输出 行,每行一个整数表示对应询问的答案。
样例 1
输入:
3 2 5
1 2 2
2 3 5
1 2
1 3
2 3
3 2
1 1
输出:
2
5
5
5
0
样例 1 解释: 第 天道路 建成,城市 连通;第 天道路 建成,三座城市全部连通。因此城市 的连通块达到大小 的最早日期是 ,达到大小 的最早日期是 ;城市 的情况同理; 时答案为 。
样例 2
输入:
4 2 5
1 2 1
3 4 2
1 2
1 3
3 2
1 1
2 4
输出:
1
-1
2
0
-1
样例 2 解释: 第 天城市 连通,第 天城市 连通,但两组城市之间始终没有道路。因此城市 的连通块永远无法达到大小 ,城市 的连通块永远无法达到大小 ;城市 的连通块在第 天达到大小 。
数据范围
对于全部测试数据:;;;;,;。
子任务
| 子任务 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 20 | |
| 2 | 所有 相等 | |
| 3 | ,且最终所有城市连通 | |
| 4 | 40 | 无特殊限制 |
提示: 注意 的询问;答案只与城市 所在的连通块有关,与另一座城市无关。