很久以前，在一个遥远的王国里，有两位国王共同统治着他们的领土。这个王国拥有 $N$ 个城镇，城镇之间由无向道路连接。每位国王拥有一部分互不相交的道路，且他们共同拥有所有的道路。已知每位国王恰好拥有 $N-1$ 条道路，并且仅使用这些道路，就能从任意一个城镇到达其他任何城镇。同一对城镇之间可能存在多条道路。

在这个故事中，还有一位魔王，他有一天决定征服这个王国。为了更容易地征服王国，一个众所周知的策略是分裂它。因此，魔王想要知道，他最少需要摧毁多少条道路，才能使得存在某一对城镇 $X$ 和 $Y$，满足无法从 $X$ 到达 $Y$。他还想知道，以最少数量摧毁道路的方法有多少种。

你的任务是找出这两个数字：魔王为了分裂王国所必须摧毁的最少道路数量，以及他实现这一目标的方案数。由于摧毁道路的方案数可能非常大，请输出其对 $1\,000\,000\,007$ ($10^9 + 7$) 取模后的结果。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 10^5$)。

接下来的 $N-1$ 行，每行包含两个整数 $a_i, b_i$，表示第一位国王拥有连接城市 $a_i$ 和 $b_i$ 的道路 ($1 \le a_i, b_i \le N$)。

接下来的 $N-1$ 行，每行包含两个整数 $a_i, b_i$，表示第二位国王拥有连接城市 $a_i$ 和 $b_i$ 的道路 ($1 \le a_i, b_i \le N$)。

输出格式

输出两个整数，分别表示为了使图不连通所需要摧毁的最少道路数量，以及实现该方案的方法数（对 $10^9 + 7$ 取模）。

样例

样例输入 1

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

样例输出 1

2 2

样例输入 2

2 
1 2 
1 2

样例输出 2

2 1