prithivMLmods/Coder-Stat

1 2 3 4<h1><font color="#000000">Problem E:</font> The Most Powerful Spell</h1>5<!-- end en only -->6 7 8 9<!-- begin en only -->10<p>11Long long ago, there lived a wizard who invented a lot of "magical patterns."12In a room where one of his magical patterns is drawn on the floor,13anyone can use magic by casting magic spells!14The set of spells usable in the room depends on the drawn magical pattern.15Your task is to compute, for each given magical pattern,16the most powerful spell enabled by the pattern.17</p>18<!-- end en only -->19 20<!-- begin en only -->21<p>22A spell is a string of lowercase letters.23Among the spells, lexicographically earlier one is more powerful.24Note that a string <em>w</em> is defined to be lexicographically earlier than a string <em>u</em>25when <em>w</em> has smaller letter26in the order a&lt;b&lt;...&lt;z on the first position at which they differ,27or <em>w</em> is a prefix of <em>u</em>.28For instance, "abcd" is earlier than "abe" because 'c' &lt; 'e',29and "abe" is earlier than "abef" because the former is a prefix of the latter.30</p>31<!-- end en only -->32 33 34<!-- begin en only -->35<p>36A magical pattern is a diagram consisting of uniquely numbered <em>nodes</em> 37and <em>arrows</em> connecting them.38Each arrow is associated with its <em>label</em>, a lowercase string.39There are two special nodes in a pattern, called the <em>star node</em>40and the <em>gold node</em>.41A spell becomes usable by a magical pattern if and only if the spell emerges42as a sequential concatenation of the labels of a path from the star to the gold along the arrows.43</p>44<!-- end en only -->45 46<!-- begin en only -->47<p>48The next figure shows an example of a pattern with four nodes and49seven arrows.50</p>51<center>52<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_D2010_E-3" width="312" height="283" alt="picture: sample dataset 1">53</center>54<!-- end en only -->55 56<!--57<img src="https://judgeapi.u-aizu.ac.jp/resources/images/E-1" width="272" height="283" alt="picture: sample dataset 1">58-->59 60<!-- begin en only -->61<p>62The node 0 is the star node and 2 is the gold node.63One example of the spells that become usable by this magical pattern is "abracadabra",64because it appears in the path65</p><p>66&nbsp;&nbsp;&nbsp;&nbsp;67 0 --"abra"--&gt; 1 --"cada"--&gt; 3 --"bra"--&gt; 2.68</p><p>69Another example is "oilcadabraketdadabra",  obtained from the path70</p><p>71&nbsp;&nbsp;&nbsp;&nbsp;72 0 --"oil"--&gt; 1 --"cada"--&gt; 3 --"bra"--&gt; 2 --"ket"--&gt; 3 --"da"--&gt; 3 --"da"--&gt; 3 --"bra"--&gt; 2.73</p><p>74The spell "abracadabra" is more powerful than "oilcadabraketdadabra"75because it is lexicographically earlier.76In fact, no other spell enabled by the magical pattern is more powerful than "abracadabra".77Thus "abracadabra" is the answer you have to compute.78</p>79<!-- end en only -->80 81<!-- begin en only -->82<p>83When you cannot determine the most powerful spell, please answer "NO".84There are two such cases.85One is the case when no path exists from the star node to the gold node.86The other case is when for every usable spell there always exist more powerful spells.87The situation is exemplified in the following figure:88"ab" is more powerful than "b", and "aab" is more powerful than "ab", and so on.89For any spell, by prepending "a", we obtain a lexicographically earlier90 (hence more powerful) spell.91</p>92<!-- end en only -->93 94<center>95<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_D2010_E-2" width="242" height="123" alt="picture: sample dataset 2"/>96</center>97 98 99<h3>Input</h3>100 101 102<!-- begin en only -->103<p>104The input consists of at most 150 datasets.105Each dataset is formatted as follows.106</p>107<!-- end en only -->108 109<blockquote>110<i>n a s g</i><br>111<i>x</i><sub>1</sub> <i>y</i><sub>1</sub> <i>lab</i><sub>1</sub><br>112<i>x</i><sub>2</sub> <i>y</i><sub>2</sub> <i>lab</i><sub>2</sub><br>113...<br>114<i>x<sub>a</sub> <i>y</i><sub>a</sub> <i>lab</i><sub>a</sub></i><br>115</pre>116</blockquote>117 118<!-- begin en only -->119<p>120The first line of a dataset contains four integers.121  <i>n</i> is the number of the nodes, and <i>a</i> is the number of the arrows.122  The numbers <i>s</i> and <i>g</i> indicate the star node and the gold node, respectively.123Then <i>a</i> lines describing the arrows follow.124Each line consists of two integers and one string.125The line "<i>x<sub>i</sub></i> <i>y<sub>i</sub></i> <i>lab<sub>i</sub></i>" represents126an arrow from the node <i>x<sub>i</sub></i> to the node <i>y<sub>i</sub></i>127with the associated label <i>lab<sub>i</sub></i> .128Values in the dataset satisfy:1292 &le; <i>n</i> &le; 40,1300 &le; <i>a</i> &le; 400,1310 &le; <i>s</i>, <i>g</i>, <i>x<sub>i</sub></i>&nbsp;, <i>y<sub>i</sub></i> &lt; <i>n</i> ,132<i>s</i> &ne;<i>g</i>,133and134<i>lab<sub>i</sub></i> is a string of 1 to 6 lowercase letters.135Be careful that there may be self-connecting arrows (i.e., <i>x<sub>i</sub></i> = <i>y<sub>i</sub></i> ),136and multiple arrows connecting the same pair of nodes137(i.e., <i>x<sub>i</sub></i> = <i>x<sub>j</sub></i> and <i>y<sub>i</sub></i> = <i>y<sub>j</sub></i>138 for some <i>i</i> &ne; <i>j</i> ).139</p>140<!-- end en only -->141 142<!-- begin en only -->143<p>144The end of the input is indicated by a line containing four zeros.145</p>146<!-- end en only -->147 148 149 150<h3>Output</h3>151 152<!-- begin en only -->153<p>154For each dataset, output a line containing the most powerful spell for the magical pattern.155If there does not exist such a spell, output "NO" (without quotes).156Each line should not have any other characters.157</p>158<!-- end en only -->159 160 161 162<h3>Sample Input</h3>163 164<pre>1654 7 0 21660 1 abra1670 1 oil1682 0 ket1691 3 cada1703 3 da1713 2 bra1722 3 ket1732 2 0 11740 0 a1750 1 b1765 6 3 01773 1 op1783 2 op1793 4 opq1801 0 st1812 0 qr1824 0 r1832 1 0 11841 1 loooop1850 0 0 0186</pre>187 188 189<h3>Output for the Sample Input</h3>190 191<pre>192abracadabra193NO194opqr195NO196</pre>197 198 199