给你一棵无向树，每个节点都分配了一个魔力值 $X_i$。

一条路径的魔力值定义为该路径上所有节点的魔力值的乘积除以该路径上的节点数。例如，由魔力值为 3 和 5 的节点组成的路径，其魔力值为 7.5 ($3 \cdot 5 / 2$)。

在给定的树中，找到魔力值最小的路径，并输出该路径的魔力值。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 10^6$)，表示树中节点的数量。

接下来的 $N - 1$ 行，每行包含两个整数 $A_i$ 和 $B_i$ ($1 \le A_i, B_i \le N$)，表示由一条边连接的两个节点的编号。

接下来的 $N$ 行中，第 $i$ 行包含一个整数 $X_i$ ($1 \le X_i \le 10^9$)，表示第 $i$ 个节点的魔力值。

输出格式

以最简分数 $P/Q$ 的形式（其中 $P$ 和 $Q$ 是互质的整数）输出魔力值最小的路径的魔力值。

在所有测试数据中，保证所需的 $P$ 和 $Q$ 均小于 $10^{18}$。

数据范围

• 在占总分 24 分的测试数据中，满足 $N \le 1\,000$。
• 在另外占总分 36 分的测试数据中，不存在连接超过 2 个其他节点的节点。

样例

输入样例 1

2
1 2
3
4

输出样例 1

3/1

输入样例 2

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

输出样例 2

1/2

说明

样例 1 说明

注意，路径的起点和终点可以是同一个节点。魔力值最小的路径仅包含魔力值为 3 的节点，因此整条路径的魔力值为 $3/1$。

样例 2 说明

由编号为 2 和 4 的节点组成的路径，其魔力值为 $(1 \cdot 1) / 2 = 1/2$。这也是所有可能路径中魔力值最小的。

术语定义

• 无向树是指由 $N$ 个节点和 $N - 1$ 条无向边组成的连通图。
• 图中的路径是指连接一系列互不相同的顶点的有限边序列。