Boruto subconsciously awakened a Dojutsu (magic) in his right eye which has a lot of special powers. One of its powers includes the ability to track a target through its chakra (energy). One day while training, Boruto marks N targets, each of which has some color \(A_{i}\). Some of the targets are connected to each other, as a result of which these N targets form a colorful undirected graph G with N nodes (denoting the N targets), indexed from 1 to N and M edges (denoting the M connections between the targets), indexed from 1 to M.
Using the power of his eye, Boruto was able to find the number of distinct colors in the connected component containing any particular target. Now Boruto wants to know the number of distinct colors in the connected component containing any particular target if the connections between the targets are being removed dynamically. As he is at an early stage of learning how to use Dojutsu, he wants your help in getting the answer to this problem.
Input Format
The first line of input contains 3 space separated integers N, M and Q denoting the number of targets, the number of connections between the targets and the number of operations to be performed respectively.
The second line contains N space-separated integers, \(i^{th}\) of which denotes the color of the target i.
The next M lines contain 2 space separated integers U and V which depicts a connection between targets U and V. \(i^{th}\) line denotes the \(i^{th}\) edge.
This is followed by Q lines, each describing an operation in the following format:-
- \(1\;X\) : Remove the connection (edge) numbered X.
- \(2\;Y\) : Print the number of distinct colors in the connected component containing target (node) Y.
Output Format
The output should consist of the answer to each of the operation of the \(2^{nd}\) type printed on a new line.
Constraints
- \(1 \le N \le 10^{5}\)
- \(1 \le M,Q \le 2\times 10^{5}\)
- \(1 \le A_{i} \le 10^{2}\)
- \(1 \le U,V \le N\)
- \(1 \le X \le M\)
- \(1 \le Y \le N\)
- There are no self loops or multiple edges in the graph.
Note
If there are multiple queries for removal of the same edge, then the last such query should be considered. Also, the index of the connections does not change after removal of any of the connections between the targets.
Initially, all the targets form a single connected component, hence the total number of distinct colours is 2. Even on removing the connection 2->3, all the targets are still connected to each other, hence even after removal of this connection, the number of distinct colours is 2.
