{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You must have heard the \u0027Traveling Salesman Problem\u0027. Here we are talking about another problem named \u0027Traveling Fool Problem\u0027. Assume that there are **n** cities connected by **m** one-way roads. Each road is labeled by an uppercase English letter (i.e \u0027A\u0027 to \u0027Z\u0027). There can be multiple roads between two cities but no roads will start and end at the same city.\n\nMr traveling fool starts his journey from city **s** and he continues his journey until he reaches **t**, or he reaches a city from which **t** is unreachable. If he is in city **u**, he can choose any road that starts from **u** with equal probability.\n\nHe may visit same city/road more than once, but once he reaches **t**, he immediately stops his journey and remembers the road labels he found in his path in the same order the roads were visited. If the road labels in the path he traveled form a palindrome, he finds himself lucky. If he is unable to reach t or the road labels don\u0027t form a valid palindrome, he finds himself unlucky.\n\nGiven the cities, roads, **s** and **t**, can you find the probability of Mr. Traveling Fool being lucky?"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (≤ 100)**, denoting the number of test cases.\n\nEach case starts with a blank line. Next line contains two integers **n (2 ≤ n ≤ 12)** and **m (0 ≤ m ≤ 1000)**. Each of the next **m** lines contains two integers, **u v (0 ≤ u, v \u003c n, u ≠ v)** and an uppercase English letter **w**, meaning that there is a one-way road from city **u** to city **v** and the road label is **w**.\n\nNext line contains an integer **(1 ≤ q ≤ 150)** denoting the number of queries. Each of the next **q** lines contains two integers denoting **s t (0 ≤ s, t \u003c n, s ≠ t)**.\n"}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number first. Then for each query, print the probability as stated. Errors less than **10\u003csup\u003e-4\u003c/sup\u003e** will be ignored."}},{"title":"Sample","value":{"format":"HTML","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\u003e2\n\n4 3\n0 1 A\n1 2 A\n2 3 A\n2\n0 3\n2 0\n\n5 4\n1 2 B\n2 3 D\n2 4 A\n2 0 B\n2\n1 3\n1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\n1.000000\n0.000000\nCase 2:\n0.000000\n0.333333\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}