题目描述

有 $m$ 棵 $n$ 个点的树，它们都分别相同地用 $n-1$ 条边连接起来，也就是这 $m$ 棵树的 结构完全相同。

接下来再在树与树之间添加 $m-1$ 条边使得这 $m$ 棵树连通，则得到一棵点数为 $n\times m$ 的大树，以第一棵树的根作为整棵大树的根。

在树上通过一条边 $u\to v$ 时，若 $dep_v<dep_u$，则花费是 $2$，否则花费是 $1$。

求在这棵大树上任意一点 $u$ 通过树上最短路径到达任意一点 $v$ 的 最大花费 以及能达到这个最大花费的 $(u,v)$ 的 数量。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行两个整数 $n,m$，表示每棵树的点数以及树的数量。

接下来 $n-1$ 行，每行两个数 $u,v$，表示每棵树上都有一条边 $(u,v)$。

接下来 $m-1$ 行，每行四个数 $x,a,y,b$，表示第 $x$ 棵树的结点 $a$ 与第 $y$ 棵树的结点 $b$ 之间有连边。

输出格式

共 $T$ 行，第 $i$ 行两个整数，分别表示最大花费和对应点对的数量。

2
3 3
3 1
2 1
3 1 2 2
1 3 2 1
3 8
3 1
2 3
4 3 3 1
3 1 2 3
6 2 1 3
8 3 7 3
5 3 7 3
6 3 7 2
8 3 2 2

11 2
22 3

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m\leq 5\times 10^4$，$1\leq \sum n+\sum m\leq 10^6$，$1\leq x,y\leq n$，$1\leq a,b\leq m$。