455-C-Statement.html

<div class="ttypography">
 <div class="problem-statement">
  <div class="header">
   <div class="title">
    C. Civilization
   </div>
   <div class="time-limit">
    <div class="property-title">
     time limit per test
    </div>1 second
   </div>
   <div class="memory-limit">
    <div class="property-title">
     memory limit per test
    </div>256 megabytes
   </div>
   <div class="input-file">
    <div class="property-title">
     input
    </div>standard input
   </div>
   <div class="output-file">
    <div class="property-title">
     output
    </div>standard output
   </div>
  </div>
  <div>
   <p>Andrew plays a game called "Civilization". Dima helps him.</p>
   <p>The game has <span class="tex-span"><i>n</i></span> cities and <span class="tex-span"><i>m</i></span> bidirectional roads. The cities are numbered from <span class="tex-span">1</span> to <span class="tex-span"><i>n</i></span>. Between any pair of cities there either is a single (unique) path, or there is no path at all. A path is such a sequence of distinct cities <span class="tex-span"><i>v</i><sub class="lower-index">1</sub>, <i>v</i><sub class="lower-index">2</sub>, ..., <i>v</i><sub class="lower-index"><i>k</i></sub></span>, that there is a road between any contiguous cities <span class="tex-span"><i>v</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>v</i><sub class="lower-index"><i>i</i> + 1</sub></span> (<span class="tex-span">1 ≤ <i>i</i> &lt; <i>k</i></span>). The length of the described path equals to <span class="tex-span">(<i>k</i> - 1)</span>. We assume that two cities lie in the same region if and only if, there is a path connecting these two cities.</p>
   <p>During the game events of two types take place:</p>
   <ol> 
    <li> Andrew asks Dima about the length of the longest path in the region where city <span class="tex-span"><i>x</i></span> lies. </li>
    <li> Andrew asks Dima to merge the region where city <span class="tex-span"><i>x</i></span> lies with the region where city <span class="tex-span"><i>y</i></span> lies. If the cities lie in the same region, then no merging is needed. Otherwise, you need to merge the regions as follows: choose a city from the first region, a city from the second region and connect them by a road so as to minimize the length of the longest path in the resulting region. If there are multiple ways to do so, you are allowed to choose any of them. </li>
   </ol>
   <p>Dima finds it hard to execute Andrew's queries, so he asks you to help him. Help Dima.</p>
  </div>
  <div class="input-specification">
   <div class="section-title">
    Input
   </div>
   <p>The first line contains three integers <span class="tex-span"><i>n</i></span>, <span class="tex-span"><i>m</i></span>, <span class="tex-span"><i>q</i></span> (<span class="tex-span">1 ≤ <i>n</i> ≤ 3·10<sup class="upper-index">5</sup></span>; <span class="tex-span">0 ≤ <i>m</i> &lt; <i>n</i></span>; <span class="tex-span">1 ≤ <i>q</i> ≤ 3·10<sup class="upper-index">5</sup></span>) — the number of cities, the number of the roads we already have and the number of queries, correspondingly.</p>
   <p>Each of the following <span class="tex-span"><i>m</i></span> lines contains two integers, <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub> ≠ <i>b</i><sub class="lower-index"><i>i</i></sub>;</span> <span class="tex-span">1 ≤ <i>a</i><sub class="lower-index"><i>i</i></sub>, <i>b</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i></span>). These numbers represent the road between cities <span class="tex-span"><i>a</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>b</i><sub class="lower-index"><i>i</i></sub></span>. There can be at most one road between two cities.</p>
   <p>Each of the following <span class="tex-span"><i>q</i></span> lines contains one of the two events in the following format:</p>
   <ul> 
    <li> <span class="tex-span">1</span> <span class="tex-span"><i>x</i><sub class="lower-index"><i>i</i></sub></span>. It is the request Andrew gives to Dima to find the length of the maximum path in the region that contains city <span class="tex-span"><i>x</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>x</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i></span>). </li>
    <li> <span class="tex-span">2</span> <span class="tex-span"><i>x</i><sub class="lower-index"><i>i</i></sub></span> <span class="tex-span"><i>y</i><sub class="lower-index"><i>i</i></sub></span>. It is the request Andrew gives to Dima to merge the region that contains city <span class="tex-span"><i>x</i><sub class="lower-index"><i>i</i></sub></span> and the region that contains city <span class="tex-span"><i>y</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">1 ≤ <i>x</i><sub class="lower-index"><i>i</i></sub>, <i>y</i><sub class="lower-index"><i>i</i></sub> ≤ <i>n</i></span>). Note, that <span class="tex-span"><i>x</i><sub class="lower-index"><i>i</i></sub></span> can be equal to <span class="tex-span"><i>y</i><sub class="lower-index"><i>i</i></sub></span>. 
     <ul></ul></li>
   </ul>
  </div>
  <div class="output-specification">
   <div class="section-title">
    Output
   </div>
   <p>For each event of the first type print the answer on a separate line.</p>
  </div>
  <div class="sample-tests">
   <div class="section-title">
    Examples
   </div>
   <div class="sample-test">
    <div class="input">
     <div class="title">
      Input
     </div>
     <pre>6 0 6<br>2 1 2<br>2 3 4<br>2 5 6<br>2 3 2<br>2 5 3<br>1 1<br></pre>
    </div>
    <div class="output">
     <div class="title">
      Output
     </div>
     <pre>4<br></pre>
    </div>
   </div>
  </div>
 </div>
</div>