{"trustable":true,"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":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eFor a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation.\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/0b358d451f5a955607b5976d41268393?v\u003d1714254382\"\u003e\u003c/center\u003e\u003cbr\u003e \u003cbr\u003eGiven a complete graph of n nodes with all nodes and edges weighted, your task is to find a tree, which is a sub-graph of the original graph, with m nodes and whose ratio is the smallest among all the trees of m nodes in the graph.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Input contains multiple test cases. The first line of each test case contains two integers n (2\u0026lt;\u003dn\u0026lt;\u003d15) and m (2\u0026lt;\u003dm\u0026lt;\u003dn), which stands for the number of nodes in the graph and the number of nodes in the minimal ratio tree. Two zeros end the input. The next line contains n numbers which stand for the weight of each node. The following n lines contain a diagonally symmetrical n×n connectivity matrix with each element shows the weight of the edge connecting one node with another. Of course, the diagonal will be all 0, since there is no edge connecting a node with itself.\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003eAll the weights of both nodes and edges (except for the ones on the diagonal of the matrix) are integers and in the range of [1, 100].\u003cbr\u003e\u003cbr\u003eThe figure below illustrates the first test case in sample input. Node 1 and Node 3 form the minimal ratio tree. \u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/20df8f815f0a2db9e6a8f88c2fa5df7a?v\u003d1714254382\"\u003e\u003c/center\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case output one line contains a sequence of the m nodes which constructs the minimal ratio tree. Nodes should be arranged in ascending order. If there are several such sequences, pick the one which has the smallest node number; if there\u0027s a tie, look at the second smallest node number, etc. Please note that the nodes are numbered from 1 . "}},{"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\u003e3 2\r\n30 20 10\r\n0 6 2\r\n6 0 3\r\n2 3 0\r\n2 2\r\n1 1\r\n0 2\r\n2 0\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}