Magical Park Transformation

You are given a park with n rest points (numbered from 1 to n) and m bidirectional edges connecting two different rest points. The park is initially a forest (i.e. there are no cycles). All edges have length 1. The longest path of a connected region (i.e. a tree) is defined as the maximum number of edges in any simple path in that region.

HXY, a perfectionist, plans to transform the park by performing q operations. There are two types of operations:

1. For a given rest point x, query the length of the longest path (i.e. the diameter) among all rest points that are mutually reachable with x.

2. For two rest points x and y, if they are already in the same connected region, ignore the operation. Otherwise, HXY will magically connect the two regions. More precisely, from the region containing x and the region containing y (each containing all nodes reachable from x or y respectively), she will choose one rest point from each region and add an edge between them. The choice is made so that the diameter of the new connected region is minimized. It can be shown that the new diameter will be \[ \max\Big(d_1,\,d_2,\,\Big\lceil\frac{d_1}{2}\Big\rceil+\Big\lceil\frac{d_2}{2}\Big\rceil+1\Big), \] where \(d_1\) and \(d_2\) are the diameters of the two regions before the merge.

You are to process the q operations. For an operation of type 1, output the current diameter of the region that contains the given rest point.

Input Notes: The initial m edges form a forest (i.e. no cycles exist). Note that the edges in the initial park are arbitrary, so the diameter of each initial region is defined in the usual sense: the length (in edges) of the longest simple path in that tree.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10^5, 0 ≤ m < n), representing the number of rest points and the number of edges in the initial park.

Each of the next m lines contains two integers u and v (1 ≤ u,v ≤ n, u ≠ v) representing an edge between rest points u and v.

The next line contains an integer q (1 ≤ q ≤ 10^5), representing the number of operations.

Each of the next q lines describes an operation:

• If the line starts with 1 followed by an integer x, it represents a type-1 query operation.
• If the line starts with 2 followed by two integers x and y, it represents a type-2 (union) operation.

It is guaranteed that in each type-2 operation, if x and y are already in the same region, the operation should be ignored.

outputFormat

For each operation of type 1, output a single integer on a new line: the diameter of the connected region that contains the given rest point.

sample

5 3
1 2
2 3
4 5
5
1 1
1 4
2 3 4
1 4
1 5

2
1
3
3