Mag

Σας δίνεται ένα μη κατευθυνόμενο δέντρο~^1~ με κάθε κόμβο του να έχει εκχωρηθεί μια μαγεία ~X_i~.

Η μαγεία ενός μονοπατιού~^2~ ορίζεται ως το γινόμενο της μαγείας των κόμβων σε αυτό το μονοπάτι διαιρούμενο με τον αριθμό των κόμβων στη διαδρομή. Για παράδειγμα, η μαγεία μιας διαδρομής που αποτελείται από κόμβους με μαγεία ~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)~, τη μαγεία του κόμβου.

Έξοδος

Εξάγετε τη μαγεία της διαδρομής με ελάχιστη μαγεία με τη μορφή ενός εντελώς μειωμένου κλάσματος ~\frac{P}{Q}~ (το ~P~ και το ~Q~ είναι αμοιβαία πρώτοι ακέραιοι αριθμοί). Σε όλες τις περιπτώσεις δοκιμής, θα ισχύει ότι τα απαιτούμενα ~P~ και ~Q~ είναι μικρότερα από ~10^{18}~.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 24 πόντων, θα ισχύει ~N \le 1\,000~. Σε περιπτώσεις δοκιμής αξίας 36 επιπλέον πόντων συνολικά, δεν θα υπάρχει κόμβος που να συνδέεται με περισσότερους από 2 άλλους κόμβους.

Παραδείγματα

input

2
1 2
3
4

output

3/1

Επεξήγηση του 1ου παραδείγματος:

Παρατηρήστε ότι η διαδρομή μπορεί να ξεκινά και να τελειώνει στον ίδιο κόμβο. Το μονοπάτι με την ελάχιστη μαγεία αποτελείται από τον κόμβο με μαγεία 3, επομένως η μαγεία ολόκληρης της διαδρομής είναι 3 / 1.

input

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

output

1/2

Επεξήγηση του 2ου παραδείγματος:

Η διαδρομή που αποτελείται από κόμβους με ετικέτες 2 και 4 έχει μαγεία (1⋅1) / 2 = 1 / 2. Αυτός είναι και ο δρόμος με την ελάχιστη δυνατή μαγεία.

~^1~ Ένα μη κατευθυνόμενο δέντρο είναι ένα συνδεδεμένο γράφημα που αποτελείται από ~N~ κόμβους και ~N - 1~ μη κατευθυνόμενες ακμές.

~^2~ Μια διαδρομή σε ένα γράφο είναι μια πεπερασμένη ακολουθία ακμών που συνδέουν μια ακολουθία κόμβων) που είναι όλες διαφορετικές μεταξύ τους

<!----Fix the Κόμβων link>