{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/52c77c52da507c20c97d6e849cf06454?v\u003d1715870728\" alt\u003d\"/problems/ironcoal/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eThere are many excellent strategy board games, and your\n favourite among them is called “Steel Age”. It offers many\n different paths to victory but you prefer the\n blood-and-fire-strategy: build as many soldiers as possible and\n club your opposition into submission. To be able to build\n soldiers you need two resources: iron ore and coal.\n\n \u003cp\u003eThe board consists of different cells numbered from\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e which can contain resources. The\n rules for moving from one cell to another are rather\n complicated: if you can move from cell A to cell B, it does not\n always mean that you can also move from B to A. For example, if\n two cells are connected by a river, then you may be able to\n move downstream, but not upstream, so long as you didn’t invent\n a steam engine; however, it still could be possible to reach\n the upstream cell by using roads and taking a detour over other\n cells.\u003c/p\u003e\n\n \u003cp\u003eAt the beginning of the game you own only one such cell,\n where all your settlers are located. At every move you are\n allowed to move an arbitrary number of settlers from a cell to\n one of its accessible neighbours. By moving your settlers into\n a cell for the first time, you “claim” it. Every claimed cell\n will bind one settler, which has to stay in this cell until the\n end of the game. However, there is no need to leave a settler\n in your initial cell because it is where your palace is located\n and thus the cell stays claimed for all time.\u003c/p\u003e\n\n \u003cp\u003eYour goal is to claim at least one cell containing the\n resource “iron ore” and at least one cell with resource “coal”\n in order to be able to build soldiers. What is the minimal\n number of settlers you need to reach this goal?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\le n \\le 10^5$\u003c/span\u003e), the number of\n cells on the playing field, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le m \u0026lt; n$\u003c/span\u003e), the number of\n cells containing iron ore, and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le k \u0026lt; n$\u003c/span\u003e), the number of\n cells containing coal.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eOne line with \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n distinct integers \u003cspan class\u003d\"tex2jax_process\"\u003e$o_1,\n \\ldots , o_ m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n o_ i \\le n$\u003c/span\u003e for all \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\le i\\le m$\u003c/span\u003e), where \u003cspan class\u003d\"tex2jax_process\"\u003e$o_1, \\ldots , o_ m$\u003c/span\u003e are the IDs\n of cells with iron ore.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eOne line with \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e\n distinct integers \u003cspan class\u003d\"tex2jax_process\"\u003e$c_1,\n \\ldots , c_ k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n c_ i \\le n$\u003c/span\u003e for all \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\le i\\le k$\u003c/span\u003e), where \u003cspan class\u003d\"tex2jax_process\"\u003e$c_1, \\ldots , c_ k$\u003c/span\u003e are the IDs\n of cells with coal.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines\n describing the topology of the board. The \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e-th line of this block\n specifies the accessible neighbours of the \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e-th cell and consists of the\n following integers:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne integer \u003cspan class\u003d\"tex2jax_process\"\u003e$0\\le a\n \\le 10$\u003c/span\u003e, the number of cells accessible from\n cell \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e distinct\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$b_1,\\dots , b_\n a$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le b_ i\n \\le n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b_ i \\ne\n j$\u003c/span\u003e for all \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\le\n i\\le a$\u003c/span\u003e), the IDs of the cells accessible from\n cell \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eIt is guaranteed, that no cell contains both resources, iron\n ore and coal. At the beginning of the game you own only the\n cell with ID \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the minimum number of settlers needed to claim at\n least one cell with coal and at least one cell with iron ore.\n Output “\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003e” if it is\n impossible to own both, coal and iron ore.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 1 1\n2\n3\n1 2\n2 3 1\n1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 1 1\n2\n3\n1 2\n1 1\n2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}