扶桑

题目描述

给定两棵 $n$ 个点的树 $T_1,T_2$，两棵树上的点分别按 $1\sim n$ 标号。

求有多少个非空集合 $S\subseteq \{1,2,3,\dots,n\}$，使得 $S$ 在 $T_1$ 上的导出子图是一条简单路径，在 $T_2$ 上的导出子图连通。

对于 $G=(V,E)$ 和 $S\subseteq V$，定义 $S$ 在 $G$ 上的导出子图 $H=(S,\{(u,v)\in E\mid u,v\in S\})$。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^5$），表示测试数据组数。接下来有 $t$ 组测试数据。每组测试数据格式如下：

第一行输入一个正整数 $n$（$2\le n\le 10^6$），代表树的点数。

接下来 $n-1$ 行，每行两个数 $u,v$，代表 $T_1$ 上的一条边。

接下来 $n-1$ 行，每行两个数 $u,v$，代表 $T_2$ 上的一条边。

所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组数据，输出一行一个数，代表答案。

样例

样例输入

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

样例输出

5
7
8