Дерево

Вам дано неорієнтоване дерево, де кожній вершині присвоєно значення магії $x_i$.

Магія шляху (шлях у графі — це кінцева послідовність різних ребер, які послідовно з'єднують вершини) визначається як добуток магії вершин на цьому шляху, поділений на кількість вершин на шляху. Наприклад, магія шляху, що складається з вершин з магією $3$ і $5$, дорівнює $7.5(\frac{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)$ — номери вершин, з'єднаних ребром.

У $i$-му з наступних $n$ рядків записано ціле число $x_i(1\le x_i\le 10^9)$ — магія $i$-ї вершини.

Вихідні дані

Виведіть магію шляху з мінімальним значенням у вигляді нескоротного дробу $P/Q(P$ і $Q$ взаємно прості числа). У всіх тестових прикладах потрібні $P$ і $Q$ менші, ніж $10^{18}$.

Приклади

Перший тест. Зверніть увагу, що шлях може починатися і закінчуватися в одному і тому ж вузлі. Шлях з мінімальною магією складається з вузла з магією $3$, тому магія всього шляху дорівнює $3/1$.

Другий тест. Шлях, що складається з вершин $2$ і $4$, є магічним $(1\cdot 1)/2=1/2$. Це також шлях з мінімально можливою магією.