Bạn được cho một cây không hướng với mỗi nút được gán một phép thuật ~X_i~. phép thuật của một đường dẫn được định nghĩa là tích của phép thuật của các nút trên đường dẫn đó chia cho 2 bởi số lượng nút trên đường dẫn. Ví dụ, phép thuật của một đường dẫn bao gồm các nút có phép thuật 3 và 5 là 7.5 (3⋅5 / 2). Trong cây được cho, hãy tìm đường dẫn có phép thuật tối thiểu và xuất ra phép thuật của đường dẫn đó.

Input

Dòng đầu tiên của đầu vào chứa số nguyên ~N (1 ≤ N ≤ 10 ^ 6)~, số lượng nút trong cây. Mỗi trong số ~N - 1~ dòng tiếp theo chứa hai số nguyên, ~A_i~ và ~B_i~ ~(1 ≤ A_i, B_i ≤ N)~, nhãn của các nút được kết nối với một cạnh. Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa số nguyên ~X_i~ ~(1 ≤ Xi ≤ 10 ^ 9)~, phép thuật của nút thứ ~i~.

Output

Xuất ra phép thuật của đường dẫn có phép thuật tối thiểu dưới dạng phân số được rút gọn hoàn toàn ~P/Q~ (~P~ và ~Q~ là các số nguyên tố cùng nhau). Trong tất cả các trường hợp kiểm tra, điều kiện sẽ giữ ~P~ và ~Q~ cần thiết nhỏ hơn ~10 ^ 18~.

score

• 24% test có ~N ≤ 1000~.
• 36% test trong đó không có nút nào được kết nối với hơn 2 nút khác.

Sample Input

2
1 2
3
4

Sample Output

3/1