TREEPAL - Tree and Palindrome

no tags 

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 a letter. The nodes of the same level are marked by the same letter.
  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 levelling is rotational.)
  5. If we take all the letters 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).

Tree Structure

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.

Equation

Input

There will be multiple testcases. The first line of each test case starts with a number N (3 <= N <= 105) which denotes the number of nodes in the tree. Next N-1 lines of the test-case each consist 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.

Sample

Input
5
1 2
1 3
2 4
3 5
6
1 2
1 3
3 4
3 5
2 6

Output
1/5
4/15

N.B. Dataset is huge, use faster IO.

Problem Setter: Syed Shahriar Manjur.

Special Thanks: Abdullah Al Maruf, Ahmad Faiyaz.


hide comments
chrisea: 2017-11-23 13:24:07

AC in one GO. Remember to use long long.

Last edit: 2017-11-23 13:27:04
(Tjandra Satria Gunawan)(曾毅昆): 2014-03-16 08:51:12

Test case is weak :-P

Ashwini: 2014-02-06 15:09:27

are we suppose to enter number of test cases in the input???

Ashwini: 2014-01-13 18:50:29

@Ahmad Faiyaz:this seems pretty easy to me.can you check why i'm getting wrong answer.
submission id:10861119
thanks in advance.


Added by:Faiyaz
Date:2013-12-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64