4131: qko 的传输

时间限制:1000 ms 内存限制:128 MB
上传者:
提交:1 通过:1

题目描述

qko 在学习计算机网络的时候,发现了一种奇怪的传输网络。这种网络可以描述为一个含有 m 条边的森林,所有的边正向流通的价值为 wi , 反向流通价值为 −wi 。如果两点联通则他们之间有通信规则。从 a 到 b 之间的通信规则 a→b在这里定义为从 a 流向 b 的价值总和,qko 需要查询其中某些点对之间是否有通信规则,但他觉得这个问题太简单了,所以交给了你。

输入格式

第 1 行一个正整数 m,表示边的数量(1 ≤ m ≤ 5 × 105 ) 第 2 行到第 m + 1 行,每行有三个正整数 xi, yi(1 ≤ xi, yi≤ 2m), wi (0 ≤ wi ≤ 103) ,表示 xi 和 yi 之间有一条边,且从 xi 到 yi 之间是正向流通的,从 yi 到 xi 是反向流通的
接下来 1 行一个正整数 k ,表示 qko 总共想要查询 k 个点对 (1 ≤ k ≤ 104) ;
接下来 k 行,每行两个正整数 q1, q2 ,表示 qko 想查询的点对信息 (1 ≤ q1, q2保证测试数据不出现环,且≤ 2m); q1, q2 在 xi 或 yi 中出现过。

输出格式

对于每一条询问,输出一行信息如下:
• 如果它们之间有通信规则,请输出通信规则 q1→q2
• 如果无通信规则,请输出 Can't reach!。

输入样例 复制

3
1 2 12
2 3 5
4 5 12
2
1 3
2 5

输出样例 复制

17
Can't reach!

数据范围与提示