prithivMLmods/Coder-Stat

1<!--<H1>Modification of Road Network</H1>-->2<h1>Road Improvement</h1>3 4<p>5Aizu is a country famous for its rich tourism resources and has <var>N</var> cities, each of which is uniquely identified with a number (0 to <var>N</var>-1). It has a road network consisting of <var>M</var> one-way roads connecting a city to another.6</p>7 8<p>9  All the roads connecting the cities in Aizu have a row of cherry trees along their routes. For enhancing the cherry-viewing experience, a proposal was made to modify the road network so that a tourist can travel around all the roads. To achieve this target, it was decided to construct several one-way roads, each connecting two cities and abiding by the following rules.10</p>11 12<ul>13<li>The newly constructed road is for one-way traffic</li>14<li>Starting from any city, a tourist is able to make a roundtrip and return to the city, whereby he/she drives all the roads exhaustively, including the newly constructed ones. Multiple passages of some of the roads are allowed.</li>15</ul>16 17<p>18  You, as a tourism promotion officer, are assigned with the task of writing a program for the road construction project.19</p>20 21<p>22  Write a program to determine the minimum number of roads to be constructed given the road network information in Aizu.23</p>24 25 26<h2>Input</h2>27 28<p>29  The input is given in the following format.30</p>31<pre>32<var>N</var> <var>M</var>33<var>s_1</var> <var>t_1</var>34<var>s_2</var> <var>t_2</var>35:36<var>s_M</var> <var>t_M</var>37</pre>38 39<p>40The first line provides the number of cities <var>N</var> (1 &le; <var>N</var> &le; 10<sup>4</sup>) and roads <var>M</var> (0 &le; <var>M</var> &le; 10<sup>5</sup>). Each of the subsequent <var>M</var> lines provides the numbers assigned to start and destination cities for the <var>i</var>-th road: <var>s_i</var>, <var>t_i</var> (0 &le; <var>s_i</var>, <var>t_i</var> &le; <var>N</var>-1) , where <var>s_i &ne; t_i</var>. (no duplicate appearance of a road)41  42</p>43 44<h2>Output</h2>45 46<p>47  Output the minimum number of roads to be newly constructed.48</p>49 50<h2>Sample Input 1</h2>51 52<pre>536 7540 2552 1561 0572 3584 3594 5605 461</pre>62 63<h2>Sample Output 1</h2>64<pre>65266</pre>67 68<h2>Sample Input 2</h2>69<pre>706 9710 2722 1731 0742 3754 3764 5775 4785 2793 480</pre>81 82<h2>Sample Output 2</h2>83<pre>84085</pre>86