{"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 \u003cp\u003eWith lifted restrictions, the border trade between Norway\n and Sweden will surely be back to its former glory. But the\n authorities are worried that this will also mean an increase of\n illegal smuggling of goods. The customs authorities of Norway\n and Sweden must cooperate to prevent this from becoming too big\n of a problem.\u003c/p\u003e\n \u003cp\u003eTo pass through the customs, one must visit a series of\n checkpoints, the Nordic Customs and Passport Control. There are\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e checkpoints in total,\n numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e is the entrance and \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e is the exit. There are\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e pairs of bidirectional\n roads that connect distinct checkpoints. The \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth checkpoint takes some amount of\n time \u003cspan class\u003d\"tex2jax_process\"\u003e$t_ i$\u003c/span\u003e to pass\n through, and this is the bottleneck in crossing the border (the\n time it takes to walk the roads is negligible).\u003c/p\u003e\n \u003cp\u003eEach checkpoint can be watched by one customs unit, either a\n Norwegian one or a Swedish one. There are \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e Norwegian customs units available,\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$n-k$\u003c/span\u003e Swedish units.\n When a road has both of its endpoints watched by customs units\n from the same country, any smugglers using that road will be\n caught. Smugglers are of course always in a hurry, and will\n always attempt to go from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e in as short amount of time as\n possible.\u003c/p\u003e\n \u003cp\u003eYour task is to decide where to put the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e customs units, so that any\n smugglers who take a fastest possible route from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e will be caught.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\leq n \\leq 10^5$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq\n m \\leq 2 \\cdot 10^5$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0\n \\leq k \\leq n$\u003c/span\u003e), the number of checkpoints, roads, and\n Norwegian customs units. The second line of input contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e positive integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$t_1, \\ldots , t_ n$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq t_ i \\leq 10^4$\u003c/span\u003e),\n the time it takes to pass through each checkpoint. Then follow\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines of input each\n containing two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq u, v \\leq n$\u003c/span\u003e), meaning that there is a road between\n checkpoints \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eIt is guaranteed that it is possible to go from any\n checkpoint to any other checkpoint using the roads. There is\n also at most one road between each pair of checkpoints, and no\n road connects a checkpoint to itself.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eIf there is a way to place the customs units so that every\n smuggler is caught, output a string of length \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, where the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth character indicates which type\n of customs unit to put at the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth checkpoint (an ‘\u003ctt class\u003d\"ttfamily\"\u003eN\u003c/tt\u003e’ for a Norwegian customs unit, and an\n ‘\u003ctt class\u003d\"ttfamily\"\u003eS\u003c/tt\u003e’ for a Swedish customs unit).\n Otherwise, if there if there is no way to catch every smuggler,\n output “\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003e”.\u003c/p\u003e\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 2 0\n1 1 1\n1 2\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eSSS\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\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\u003e2 1 1\n1 1\n1 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 \u003ch2\u003eSample 3\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\u003e8 9 4\n3 3 1 2 2 3 2 1\n1 2\n1 3\n1 4\n2 5\n3 6\n4 7\n5 8\n6 8\n7 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eSNSNSSNN\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}