prithivMLmods/Coder-Stat

1 2 3<H1>4<font color="#000">Problem F:</font> Name the Crossing5</H1>6 7<P>8The city of Kyoto is well-known for its Chinese plan: streets are9either North-South or East-West. Some streets are numbered, but most10of them have real names.11<br>12Crossings are named after the two streets crossing there,13e.g. Kawaramachi-Sanjo is the crossing of Kawaramachi street and Sanjo14street. But there is a problem: which name should come first?15At first the order seems quite arbitrary: one says Kawaramachi-Sanjo16(North-South first) but Shijo-Kawaramachi (East-West first). With some17experience, one realizes that actually there18seems to be an "order" on the streets, for instance in the above19Shijo is "stronger" than Kawaramachi, which in turn is "stronger" than20Sanjo.21One can use this order to deduce the names of other crossings.22</P>23 24 25 26<P>27You are given as input a list of known crossing names X-Y.28Streets are either North-South or East-West, and only orthogonal streets29may cross.30</P>31<P>32As your list is very incomplete, you start by completing it using33the following rule:34</P>35<ul>36<li>37  two streets A and B have <i>equal strength</i> if (1) to (3) are38  all true:39<ol>40<li> they both cross the same third street C in the input </li>41<li> there is no street D such that D-A and B-D appear in the input </li>42<li> there is no street E such that A-E and E-B appear in the input </li>43</ol>44</li>45</ul>46<P>47We use this definition to extend our strength relation:48</P>49<ul>50<li>51  A is <i>stronger</i> than B, when there is a52  sequence A = A<sub>1</sub>, A<sub>2</sub>, ..., A<sub><i>n</i></sub> = B,53  with <i>n</i> at least 2, <br>54  where, for any <i>i</i> in 1 .. <i>n</i>-1, either55  A<sub><i>i</i></sub>-A<sub><i>i</i>+1</sub> is an input crossing or56  A<sub><i>i</i></sub> and A<sub><i>i</i>+1</sub> have equal strength.57</li>58</ul>59<P>60Then you are asked whether some other possible crossing names X-Y are61valid. You should answer affirmatively if you can infer the validity of a62name, negatively if you cannot. Concretely:63</P>64<ul>65<li>66  YES    if you can infer that the two streets are orthogonal, and X67         is stronger than Y68</li>69<li>70  NO     otherwise71</li>72</ul>73 74 75<H2>Input</H2>76 77 78<P>79The input is a sequence of data sets, each of the form80</P>81<blockquote>82<pre><i>N83Crossing<sub>1</sub>84...85Crossing<sub>N</sub>86M87Question<sub>1</sub>88...89Question<sub>M</sub>90</i></pre>91</blockquote>92<P>93Both <i>Crossing</i>s and <i>Question</i>s are of the form94</P>95<blockquote>96<i>X-Y</i>97</blockquote>98<P>99where <i>X</i> and <i>Y</i> are strings of alphanumerical characters,100of lengths no more than 16. There is no white space, and case matters101for alphabetical characters.102<br>103<i>N</i> and <i>M</i> are between 1 and 1000 inclusive, and there are104no more than 200 streets in a data set.105</P>106<P>107The last data set is followed by a line containing a zero.108</P>109 110 111<H2>Output</H2>112 113 114<P>115The output for each data set should be composed of <i>M</i>+1 lines,116the first one containing the number of streets117in the <i>Crossing</i> part of the input, followed by the answers to118each question, either YES or NO without any spaces.119</P>120 121 122<H2>Sample Input</H2>123<PRE>1247125Shijo-Kawaramachi126Karasuma-Imadegawa127Kawaramachi-Imadegawa128Nishioji-Shijo129Karasuma-Gojo130Torimaru-Rokujo131Rokujo-Karasuma1326133Shijo-Karasuma134Imadegawa-Nishioji135Nishioji-Gojo136Shijo-Torimaru137Torimaru-Gojo138Shijo-Kawabata13941401jo-Midosuji141Midosuji-2jo1422jo-Omotesando143Omotesando-1jo1444145Midosuji-1jo1461jo-Midosuji147Midosuji-Omotesando1481jo-1jo1490150</PRE>151 152<H2>Output for the Sample Input</H2>153<PRE>1548155YES156NO157YES158NO159YES160NO1614162YES163YES164NO165NO166</PRE>167 168 169 170