Cut and Find Queries on a Tree

You are given a tree with \(n\) nodes labeled from 1 to \(n\) and \(n-1\) edges. Initially, all nodes are connected as a single tree. You will then receive a number of queries. There are two types of queries:

• cut u v: Remove the edge connecting nodes \(u\) and \(v\). It is guaranteed that this edge exists in the current tree.
• find u: Find and output the smallest numbered node in the connected component containing node \(u\).

Note: After a cut operation, the tree might split into two components, so that subsequent find queries will reflect the updated connectivity.

Input/Output Format: The input is given via standard input and output via standard output.

Example:

Input:
5
1 2
1 3
3 4
3 5
3
cut 3 4
find 4
find 3
Output:
4
1

</p>

inputFormat

The first line contains an integer \(n\) (\(2 \leq n \leq 10^5\)), the number of nodes.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge between node \(u\) and node \(v\).

The following line contains an integer \(q\), the number of queries.

The next \(q\) lines each contain a query in one of the following forms:

• cut u v
• find u

It is guaranteed that all cut operations refer to an edge that exists in the current tree.

outputFormat

For each find query, output the smallest numbered node in the connected component containing the queried node on a separate line.

## sample

5
1 2
1 3
3 4
3 5
3
cut 3 4
find 4
find 3

4
1

</p>