You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目限制

2000 ms 256 M

题目描述

小A和小C要在不同的树上进行攀爬比赛。现在选了两颗节点数同为n的树，节点分别以1~n标号（根节点标号为1），但两棵树的节点连接方式不完全相同。

现在他们决定选择两个标号的点进行比赛，且规定过程中必须都向上爬（即选定的赛段节点u →节点v都必须指向叶子方向），请你求出这两棵树上共有多少对节点满足比赛的需求。

输入格式

第一行一个数n。（ n≤100000）

接下来n-1行，每行2个数a和b，表示第一棵树a和b有树枝相连。

接下来n-1行，每行2个数a和b，表示第二棵树a和b有树枝相连。

输出格式

输出满足条件的对数。

数据范围

对于30%的数据： n≤1000

对于50%的数据： n≤10000

对于100%的数据： n≤100000， 1≤a,b≤n

输入​输出​样例

输入样例1

4

1 2

2 3

3 4

1 2

2 3

2 4

输出样例1

5

输入样例2

7

1 2

1 3

2 4

1 5

5 6

6 7

1 2

1 3

3 4

4 5

3 6

1 7

输出样例2

6

输入样例3

4

1 2

1 3

3 4

1 2

1 3

3 4

输出样例3

4