Cycle Graph Queries

Given a cycle graph with n nodes and n edges, where each node i has an associated label, you are to process a series of queries on the graph. The graph is guaranteed to contain exactly one cycle. Each query is one of the following:

• Type 1: 1 u v – Swap the labels of nodes u and v.
• Type 2: 2 u v – Find the maximum label along the shortest path between nodes u and v.

Note that, in a cycle graph, there is a unique shortest path between any two nodes.

inputFormat

The input is given as follows:

• Line 1: An integer n representing the number of nodes.
• Line 2: n space-separated integers representing the labels of the nodes.
• Next n lines: Each line contains two integers u and v representing an undirected edge between nodes u and v.
• The following line contains an integer q representing the number of queries.
• Next q lines: Each line contains three integers t u v. If t = 1, swap the labels of nodes u and v. If t = 2, output the maximum label along the shortest path from u to v.

outputFormat

For each query of Type 2, output a single line containing the maximum label found along the shortest path between the given nodes.

## sample

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

4
6

</p>