问题描述

须佳君住在一个由N个车站组成的国家。这个国家只有A公司和B公司两家铁路公司，它们各自建造自己的铁路线。

这些铁路线连接了两个车站，每条线路都有一个长度。无论是A公司还是B公司，都使用自己的线路，在两个车站之间只经过自己公司的线路，而不重复使用同一条线路2次或更多次。已知对于任意两个车站，存在且只存在一种这样的路径。

因此，每个公司都根据自己公司所建造线路的特性，将第i个车站和第j个车站之间的移动费用定义为通过相邻车站之间的距离的最大值。

须佳君在考虑不同的2个车站之间的移动时，思考应该选择哪家铁路公司更好。然后，他想知道在某些不同车站之间的移动中，无论选择哪家铁路公司，费用是否相同。他打算计算这样的车站组合的数量。

那么，到底有多少种车站组合的费用既适用于公司A又适用于公司B呢？

输入

从标准输入读取输入数据，其格式如下：

$N$ $a_1$ $b_1$ $p_1$ $a_2$ $b_2$ $p_2$ ... $a_{N-1}$ $b_{N-1}$ $p_{N-1}$ $c_1$ $d_1$ $q_1$ $c_2$ $d_2$ $q_2$ ... $c_{N-1}$ $d_{N-1}$ $q_{N-1}$

• 第一行表示车站的数量N（1≦N≦100000）。
• 接下来的N-1行表示A公司构建的线路信息，描述了A公司建造的从第$a_i$（1≦$a_i$≦N）个车站到第$b_i$（1≦$b_i$≦N）个车站的长度为$p_i$（1≦$p_i$≦$10^9$）的线路。
• 接下来的N-1行表示B公司构建的线路信息，描述了B公司建造的从第$c_i$（1≦$c_i$≦N）个车站到第$d_i$（1≦$d_i$≦N）个车站的长度为$q_i$（1≦$q_i$≦$10^9$）的线路。

分数

本问题有部分得分。对于满足以下约束条件的数据集给出正确答案的话，将获得40分。

• 同一家铁路公司不会建造相同长度的线路。

输出

输出符合无论使用哪家铁路公司费用都不变的车站组合的数量。请以一行输出，不要忘记换行符。

输入样例1

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

输出样例1

1

输入样例2

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

输出样例2

2

输入样例3

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

输出样例3

10
```这是满足部分得分的约束条件的情况。