{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eRoman adores all kinds of labyrinths. He solves them since his early childhood.\r\nYesterday he found a new, extremely amazing sort of labyrinth. He called it a \"fractal labyrinth\".\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eImagine a house with \u003ci\u003eN\u003c/i\u003e doors. Inside it, there are \u003ci\u003eK\u003c/i\u003e houses, each of them an entire copy of the \"outer\" one. Some doors are connected by roads. If you draw these roads, you get something like this:\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_centered_picture\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/d4c78ae7e7e863087cad750e11758fb5?v\u003d1714916147\" border\u003d\"0\" alt\u003d\"Problem illustration\"\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eRemembering that each \"inner\" house is a copy of the \"outer house\", you get the following picture \r\nas a result:\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_centered_picture\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/35074a15d11ba67c551b7c3c4d4e6e15?v\u003d1714916147\" border\u003d\"0\" alt\u003d\"Problem illustration\"\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe following picture is an example of a house with 2 inner houses:\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_centered_picture\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/a5e9dafefe782416762059dc11983c64?v\u003d1714916147\" border\u003d\"0\" alt\u003d\"Problem illustration\"\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFor outer house, some door is defined as \"input\" and some door as \"output\", so we finally come up to a labyrinth. Assuming that length of each road is 1, find the length of the shortest path in such labyrinth.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn the first line there are numbers \u003ci\u003eN\u003c/i\u003e \u003cnobr\u003e(2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 20)\u003c/nobr\u003e and \u003ci\u003eK\u003c/i\u003e \u003cnobr\u003e(0 ≤ \u003ci\u003eK\u003c/i\u003e ≤ 5)\u003c/nobr\u003e. The next line contains \u003ci\u003eM\u003c/i\u003e, the number of the roads. In the following \u003ci\u003eM\u003c/i\u003e lines there are descriptions of the roads, one per line.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEach road description is formatted in the following way: \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par_pre\"\u003e\u003cpre\u003e\u0026lt;house-number\u0026gt;.\u0026lt;door-number\u0026gt; - \u0026lt;house-number\u0026gt;.\u0026lt;door-number\u0026gt;\u003c/pre\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003ewhere left and right part of description specify the connected doors (a door is described by its number and\r\nnumber of house it belongs to). Each road is bidirectional. The \"outer\" house has number 0, \"inner\" houses have numbers from 1 to \u003ci\u003eK\u003c/i\u003e. Door numbers start with 0. No two roads connect the same pair of doors. No road connects a door to itself.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn the last line there are numbers of input and output door \u003ci\u003eD\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eD\u003csub\u003eo\u003c/sub\u003e\u003c/i\u003e. These numbers may coincide.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf there exists a path from input to output, print the minimal length of such path. Otherwise, print \"no\u0026nbsp;solution\".\u003c/div\u003e\u003c/div\u003e"}},{"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\u003e12 1\r\n11\r\n0.0 - 1.1\r\n0.1 - 0.2\r\n1.2 - 1.3\r\n0.3 - 0.4\r\n1.4 - 1.5\r\n0.5 - 0.6\r\n1.6 - 1.7\r\n0.7 - 0.8\r\n1.8 - 1.9\r\n0.9 - 0.10\r\n1.10 - 0.11\r\n0 11\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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\u003e8 0\r\n8\r\n0.0 - 0.2\r\n0.1 - 0.3\r\n0.2 - 0.4\r\n0.3 - 0.5\r\n0.4 - 0.6\r\n0.5 - 0.7\r\n0.6 - 0.0\r\n0.7 - 0.1\r\n2 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eno solution\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}