{"trustable":false,"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":"\u003cp\u003eTo get from the country of the South Emperor to the country of the NorthEmperor, one must visit a complex set of checkpoints at the border. In total, there are \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e checkpoints and they are labeled from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. We know that checkpoint \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e is always the entrance and checkpoint \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e is the exit. Connecting the distinct checkpoints, we have \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e pairs of bidirectional paths. We also know that at each checkpoint we need to wait some amount of time, i.e. at \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth checkpoint we require \u003cspan class\u003d\"tex2jax_process\"\u003e$t_ i$\u003c/span\u003e to pass through. Compared to these amounts of time, walking the paths between two distinct checkpoints can be neglected (is equal to zero).\n\u003c/p\u003e \n\u003cp\u003eAll checkpoints are guarded by officers from either the North Emperor or from the South Emperor: \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e from the North, and \u003cspan class\u003d\"tex2jax_process\"\u003e$n-k$\u003c/span\u003e from the South. When a path between two checkpoints is watched by officers from different countries, they talk more with news from their countries and are less attentive to illegal trafficking. On another hand, if they are from the same country they always catch any illegal traffic across the border.\n\u003c/p\u003e\n\u003cp\u003eKnowing that illegal traffic takes place as fast as possible, thus preferring to get from entrance \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to exit\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e in as short an amount of time as possible, you have to determine how to place the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e ccustoms units from the two different countries, so that any illegal traffic taking a fastest possible route from border entrance \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to exit \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 contains three integers: the number of checkpoints \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, the number of paths \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e, and the number of North Emperor customs units \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq n \\leq 10^5$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq m \\leq 2 \\cdot 10^5$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq k \\leq n$\u003c/span\u003e). The second line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e positive integers \u003cspan class\u003d\"tex2jax_process\"\u003e$t_1, \\ldots , t_ n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq t_ i \\leq 10^4$\u003c/span\u003e), denoting the time to pass through each checkpoint. Then follow the \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e paths, one on its own line consisting of a pair of 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 \\leq u, v \\leq n$\u003c/span\u003e), the endpoints of the current path.\u003c/p\u003e \n\u003cp\u003eWe know that it is possible to go from any checkpoint to any other checkpoint using the set of paths, that there is at most one path between each pair of checkpoints, and no path connects a checkpoint to itself.\u003c/p\u003e \n\u003ch2\u003eOutput\u003c/h2\u003e \n\u003cp\u003eIf we can find a way to arrange the customs units so that any illegal border traffic 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 denotes the country of the customs unit assigned at the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth checkpoint (‘\u003ctt class\u003d\"ttfamily\"\u003eN\u003c/tt\u003e’ for North Emperor, ‘\u003ctt class\u003d\"ttfamily\"\u003eS\u003c/tt\u003e’ for South Emperor). Otherwise, output “\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003e”.\u003c/p\u003e \n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 1\u003c/th\u003e \n \u003cth\u003eSample Output 1\u003c/th\u003e \n \u003c/tr\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\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 2\u003c/th\u003e \n \u003cth\u003eSample Output 2\u003c/th\u003e \n \u003c/tr\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\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 3\u003c/th\u003e \n \u003cth\u003eSample Output 3\u003c/th\u003e \n \u003c/tr\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"}}]}