prithivMLmods/Coder-Stat

1<h2>Eulerian Flight Tour</h2>2 3<p>4  You have an airline route map of a certain region. All the airports in the region and all the <i>non-stop routes</i> between them are on the map. Here, a non-stop route is a flight route that provides non-stop flights in both ways.5</p>6 7<p>8  Named after the great mathematician Leonhard Euler, an <i>Eulerian tour</i> is an itinerary visiting all the airports in the region taking a single flight of every non-stop route available in the region. To be precise, it is a list of airports, satisfying all of the following.9</p>10 11<ul>12<li> The list begins and ends with the same airport.</li>13<li> There are non-stop routes between pairs of airports adjacent in the list.</li>14<li> All the airports in the region appear <i>at least once</i> in the list. Note that it is allowed to have some airports appearing multiple times.</li>15<li> For all the airport pairs with non-stop routes in between, there should be <i>one and only one adjacent appearance</i> of two airports of the pair in the list in either order.</li>16</ul>17 18<p>19  It may not always be possible to find an Eulerian tour only with the non-stop routes listed in the map. Adding more routes, however, may enable Eulerian tours. Your task is to find a set of additional routes that enables Eulerian tours.20</p>21 22 23<h3>Input</h3>24<p>25  The input consists of a single test case.26</p>27<pre>28$n$ $m$29$a_1$ $b_1$30...31$a_m$ $b_m$32</pre>33 34<p>35  $n$ ($3 \leq n \leq 100$) is the number of airports. The airports are numbered from 1 to $n$. $m$ ($0 \leq m \leq \frac{n(n-1)}{2}$) is the number of pairs of airports that have non-stop routes. Among the $m$ lines following it, integers $a_i$ and $b_i$ on the $i$-th line of them ($1 \leq i \leq m$) are airport numbers between which a non-stop route is operated. You can assume $1 \leq a_i < b_i \leq n$, and for any $i \ne j$, either $a_i \ne a_j$ or $b_i \ne b_j$ holds.36</p>37 38<h3>Output</h3>39 40<p>41  Output a set of additional non-stop routes that enables Eulerian tours. If two or more different sets will do, any one of them is acceptable. The output should be in the following format.42</p>43 44<pre>45$k$46$c_1$ $d_1$47...48$c_k$ $d_k$49</pre>50<p>51  $k$ is the number of non-stop routes to add, possibly zero. Each of the following $k$ lines should have a pair of integers, separated by a space. Integers $c_i$ and $d_i$ in the $i$-th line ($c_i < d_i$) are airport numbers specifying that a non-stop route is to be added between them. These pairs, ($c_i, d_i$) for $1 \leq i \leq k$, should be distinct and should not appear in the input.52</p>53 54<p>55  If adding new non-stop routes can never enable Eulerian tours, output <span>-1</span> in a line.56</p>57 58 59<h3>Sample Input 1</h3>60<pre>614 2621 2633 464</pre>65<h3>Sample Output 1</h3>66<pre>672681 4692 370</pre>71 72<h3>Sample Input 2</h3>73<pre>746 9751 4761 5771 6782 4792 5802 6813 4823 5833 684</pre>85<h3>Sample Output 2</h3>86<pre>87-188</pre>89 90<h3>Sample Input 3</h3>91<pre>926 7931 2941 3951 4962 3974 5984 6995 6100</pre>101<h3>Sample Output 3</h3>102<pre>10331041 51052 41062 5107</pre>108 109<h3>Sample Input 4</h3>110<pre>1114 31122 31132 41143 4115</pre>116<h3>Sample Output 4</h3>117<pre>118-1119</pre>120 121<h3>Sample Input 5</h3>122<pre>1235 51241 31251 41262 41272 51283 5129</pre>130<h3>Sample Output 5</h3>131<pre>1320133</pre>134 135