当前没有测试数据。

Tree and Palindrome | TREEPAL

You are given a tree with N nodes. The tree has following properties

1. It is rooted at node 1




2. Node 1 situated in level 0. The children of node 1 is situated in level 1 ,  the children of the level 1 nodes is situated in level 2  , the children of the level 2 nodes is situated in level 3 and so on ….... .




3. Every node is marked by an alphabet. The nodes of the same level are marked by the same alphabet.




4. Level zero nodes are marked by 'a' , level 1 nodes are marked by 'b' , level 2 nodes are marked by 'c'

…... level 25 nodes are marked by 'z', level 26 nodes are marked again by 'a', level 27 nodes are marked by 'b' and so on … (the leveling is rotational).




5. If we take all the alphabets of the nodes serially which are in the path from node a to node b (including a, b) and concatenate them, then we find a string. The name of the string is Bokkor string of pair (a, b).

You will be given a pair of distinct nodes. You don't know in advance which pair will be given. The probability of choosing every pair is same. Now your job is to calculate the probability that the Bokkor string of the given pair is a palindrome in p/q format (where p and q are co-prime).

Figure: Tree Structure

Here the pair (2, 3) forms the Bokkor string “bab” which is a palindrome.
And the pair (4, 5) forms the Bokkor string “cbabc” which is also a palindrome.
There are no other palindromic Bokkor pairs.

Input 

There will be multiple testcases. The first line of each test case starts with a number N (3<=N<=10⁵) which denotes the number of nodes in the tree. Next N-1 line of the test-case each consists of a pair of integers u, v (1<= u, v<=N and u! = v) which denotes there is an edge between u and v. It is guaranteed that the input is legal (no multiple edges and it forms a valid tree)
 

Output
For each test case output is just a single line “p/q” (without the quotes) as described above. It is guaranteed that p>=1.

N.B. Dataset is huge, use faster IO

Problem Setter: Syed Shahriar Manjur

Special Thanks: Abdullah Al Maruf , Ahmad Faiyaz