{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You are given a tree. If we select 2 distinct nodes uniformly at random, what\u0027s the probability that the distance between these 2 nodes is a prime number?"}},{"title":"Input Format","value":{"format":"MD","content":"The first line contains a number **N**: the number of nodes in this tree.\nThe following **N**-1 lines contain pairs a[i] and b[i], which means there is an edge with length 1 between a[i] and b[i]."}},{"title":"Output Format","value":{"format":"MD","content":"Output a real number denote the probability we want.\nYou\u0027ll get accept if the difference between your answer and standard answer is no more than 10^-6."}},{"title":"Constraints","value":{"format":"MD","content":"**2** ≤ **N** ≤ **50,000** \n\nThe input must be a tree."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\n1 2\n2 3\n3 4\n4 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nWe have C(5, 2) \u003d 10 choices, and these 5 of them have a prime distance:\n\n1-3, 2-4, 3-5: 2\n\n1-4, 2-5: 3\n\nNote that 1 is not a prime number."}}]}