{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eYou are given a tree with \u003cstrong\u003eN\u003c/strong\u003e nodes. The tree has following properties\u003c/p\u003e\r\n\u003col\u003e\r\n\u003cli\u003eIt is rooted at node 1\u003c/li\u003e\r\n\r\n\u003cli\u003eNode 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.\u003c/li\u003e\r\n\r\n\u003cli\u003eEvery node is marked by a letter. The nodes of the same level are marked by the same letter.\u003c/li\u003e\r\n\r\n\u003cli\u003eLevel zero nodes are marked by \u0027a\u0027, level 1 nodes are marked by \u0027b\u0027, level 2 nodes are marked by \u0027c\u0027. Level 25 nodes are marked by \u0027z\u0027, level 26 nodes are marked again by \u0027a\u0027, level 27 nodes are marked by \u0027b\u0027 and so on. (The levelling is rotational.)\u003c/li\u003e\r\n\r\n\u003cli\u003eIf 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 \u003cstrong\u003eBokkor\u003c/strong\u003e string of pair (a, b).\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\r\n\u003cp\u003eYou will be given a pair of distinct nodes. You don\u0027t 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 \u003cstrong\u003eBokkor\u003c/strong\u003e string of the given pair is a palindrome in \u003cstrong\u003ep/q\u003c/strong\u003e format (where p and q are co-prime).\u003c/p\u003e\r\n\r\n\u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/143d0ba281262e64a7046dc91790636e?v\u003d1714303276\" alt\u003d\"Tree Structure\"\u003e\u003c/p\u003e\r\n\u003cp align\u003d\"center\"\u003eFigure: Tree Structure\u003c/p\u003e\r\n\r\n\u003cp\u003eHere 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.\u003c/p\u003e\r\n\u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/36ce9ff893bc678a99a6fca00cf0c460?v\u003d1714303276\" alt\u003d\"Equation\" width\u003d\"687\" height\u003d\"52\"\u003e\u003c/p\u003e\r\n\r\n\u003c!--[if gte msEquation 12]\u003e\u003cm:oMathPara\u003e\u003cm:oMath\u003e\u003cm:f\u003e\u003cm:fPr\u003e\u003cspan style\u003d\"font-size:14.0pt;mso-ansi-font-size:14.0pt;mso-bidi-font-size:14.0pt; font-family:\"Cambria Math\",\"serif\";mso-ascii-font-family:\"Cambria Math\"; mso-hansi-font-family:\"Cambria Math\";font-style:italic;mso-bidi-font-style: normal\" mce_style\u003d\"font-size:14.0pt;mso-ansi-font-size:14.0pt;mso-bidi-font-size:14.0pt; font-family:\"Cambria Math\",\"serif\";mso-ascii-font-family:\"Cambria Math\"; mso-hansi-font-family:\"Cambria Math\";font-style:italic;mso-bidi-font-style: normal\"\u003e\u003cm:ctrlPr\u003e\u003c/m:ctrlPr\u003e\u003c/span\u003e\u003c/m:fPr\u003e\u003cm:num\u003e\u003ci style\u003d\"mso-bidi-font-style: normal\" mce_style\u003d\"mso-bidi-font-style: normal\"\u003e\u003cspan style\u003d\"font-size:14.0pt;line-height:115%;font-family:\"Cambria Math\",\"serif\"; mso-fareast-font-family:Calibri;mso-fareast-theme-font:minor-latin; mso-bidi-font-family:Vrinda;mso-bidi-theme-font:minor-bidi;mso-ansi-language: EN-US;mso-fareast-language:EN-US;mso-bidi-language:AR-SA\" mce_style\u003d\"font-size:14.0pt;line-height:115%;font-family:\"Cambria Math\",\"serif\"; mso-fareast-font-family:Calibri;mso-fareast-theme-font:minor-latin; mso-bidi-font-family:Vrinda;mso-bidi-theme-font:minor-bidi;mso-ansi-language: EN-US;mso-fareast-language:EN-US;mso-bidi-language:AR-SA\"\u003e\u003cm:r\u003eTotal\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003enumbers\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003eof\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003eBokkor\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003epairs\u003c/m:r\u003e\u003c/span\u003e\u003c/i\u003e\u003c/m:num\u003e\u003cm:den\u003e\u003ci style\u003d\"mso-bidi-font-style: normal\" mce_style\u003d\"mso-bidi-font-style: normal\"\u003e\u003cspan style\u003d\"font-size:14.0pt;line-height:115%;font-family:\"Cambria Math\",\"serif\"; mso-fareast-font-family:Calibri;mso-fareast-theme-font:minor-latin; mso-bidi-font-family:Vrinda;mso-bidi-theme-font:minor-bidi;mso-ansi-language: EN-US;mso-fareast-language:EN-US;mso-bidi-language:AR-SA\" mce_style\u003d\"font-size:14.0pt;line-height:115%;font-family:\"Cambria Math\",\"serif\"; mso-fareast-font-family:Calibri;mso-fareast-theme-font:minor-latin; mso-bidi-font-family:Vrinda;mso-bidi-theme-font:minor-bidi;mso-ansi-language: EN-US;mso-fareast-language:EN-US;mso-bidi-language:AR-SA\"\u003e\u003cm:r\u003eTotal\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003enumbers\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003eof\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003epossible\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003cm:r\u003epairs\u003c/m:r\u003e\u003cm:r\u003e \u003c/m:r\u003e\u003c/span\u003e\u003c/i\u003e\u003c/m:den\u003e\u003c/m:f\u003e\u003c/m:oMath\u003e\u003c/m:oMathPara\u003e\u003c![endif]--\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThere will be multiple testcases. The first line of each test case starts with a number \u003cstrong\u003eN\u003c/strong\u003e \u003cstrong\u003e(3 \u0026lt;\u003d N \u0026lt;\u003d 10\u003csup\u003e5\u003c/sup\u003e)\u003c/strong\u003e which denotes the number of nodes in the tree. Next \u003cstrong\u003eN-1\u003c/strong\u003e lines of the test-case each consist of a pair of integers \u003cstrong\u003eu, v (1 \u0026lt;\u003d u, v \u0026lt;\u003d N and u !\u003d v)\u003c/strong\u003e 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.)\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case output is just a single line \u003cstrong\u003e\"p/q\"\u003c/strong\u003e (without the quotes) as described above. It is guaranteed that p\u0026gt;\u003d1.\u003c/p\u003e\r\n\r\n\u003ch3\u003eSample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n1 2\r\n1 3\r\n2 4\r\n3 5\r\n6\r\n1 2\r\n1 3\r\n3 4\r\n3 5\r\n2 6\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1/5\r\n4/15\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003cp\u003e\u003cstrong\u003eN.B. Dataset is huge, use faster IO.\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eProblem Setter: Syed Shahriar Manjur.\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eSpecial Thanks: Abdullah Al Maruf, Ahmad Faiyaz.\u003c/strong\u003e\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}