{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"给定 N 个节点的一棵树,每个点有权值。\n\n问是否能找到一条路径,使得路径上所有点的乘积对 $10^6+3$ 取模恰好等于 k。\n\n如果可以,请输出端点**最小的**一条路径。\n\n\u003cdiv class\u003d\"panel_content\"\u003e\n There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 10\u003csup\u003e6\u003c/sup\u003e + 3) equals to K?\n \u003cbr\u003eCan you help them in solving this problem?\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"MD","content":"There are several test cases, please process till EOF.\n\u003cbr\u003eEach test case starts with a line containing two integers N(1 \u0026lt;\u003d N \u0026lt;\u003d 10\u003csup\u003e5\u003c/sup\u003e) and K(0 \u0026lt;\u003dK \u0026lt; 10\u003csup\u003e6\u003c/sup\u003e + 3). The following line contains n numbers v\u003csub\u003ei\u003c/sub\u003e(1 \u0026lt;\u003d v\u003csub\u003ei\u003c/sub\u003e \u0026lt; 10\u003csup\u003e6\u003c/sup\u003e + 3), where vi indicates the integer on vertex i. Then follows N - 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y."}},{"title":"Output","value":{"format":"MD","content":"For each test case, print a single line containing two integers a and b (where a \u0026lt; b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead.\n\u003cbr\u003eFor more information, please refer to the Sample Output below."}},{"title":"Sample","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\u003e\u003cpre\u003e5 60\n2 5 2 3 3\n1 2\n1 3\n2 4\n2 5\n5 2\n2 5 2 3 3\n1 2\n1 3\n2 4\n2 5\n\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e3 4\nNo solution\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"\u003cbr\u003e1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较,若第一个数字大小相同,则按照第二个数字大小进行比较,依次类推。\n\u003cbr\u003e\n\u003cbr\u003e2. 若出现栈溢出,推荐使用C++语言提交,并通过以下方式扩栈:\n\u003cbr\u003e#pragma comment(linker,\"/STACK:102400000,102400000\")\n\u003cbr\u003e"}}]}