{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn the Middle Ages m European cities imported many goods from n Arabian cities. Due to continous feudal wars, European cities did not trade with each other, so is some European city needed some Arabian goods, the special trade route was established for this particular trade.\u003c/p\u003e\n\u003cp\u003eStudying the manuscripts historians have found out that each European city imported goods from at least two Arabian cities, and each Arabian city exported goods to at least two European cities. They have also investigated different factors and identified all potential trade routes (trade routes between some pairs of cities were impossible due to various reasons).\u003c/p\u003e\n\u003cp\u003eNow historians wonder, what is the minimal possible number of trade routes, that could have existed. Help them to find that out.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe first line of the input file contains m, n, and p - the number of European and Arabian cities respectively, and the number of potential trade routes (1 \u0026lt;\u003d m, n \u0026lt;\u003d 300, 1 \u0026lt;\u003d p \u0026lt;\u003d nm). The following p lines describe potential trade routes, each description consists of two numbers - the European and the Arabian city connected by the route.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eOn the first line of the output file print k - the minimal possible number of trade routes that could have existed. After that output k numbers - some minimal set of routes that might have existed to satisfy all conditions. Routes are numbered starting from 1 as they are given in the input file.\u003c/p\u003e\n\u003cp\u003eIf historians must have made a mistake and it is impossible to satisfy the specified conditions, print -1 on the first and the only line of the output file.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e5 5 14\n1 2\n1 3\n1 4\n1 5\n2 1\n2 5\n3 1\n3 5\n4 1\n4 5\n5 1\n5 2\n5 3\n5 4\n\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e12\n1 2 3 5 6 7 8 9 10 12 13 14\n\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cbr\u003e\n"}}]}