#include <iostream>

using namespace std;

bool** UnesiMatricu(int& n, int *map)
{
	bool** m = new bool* [n];
	int g = n - 1;

	for (int i = 0; i < n; i++)
	{
		cin >> map[i];
		m[i] = new bool[n];
		for (int j = 0; j < n; j++)
		{
			m[i][j] = 0;
		}
	}

	for (int i = 0; i < g; i++)
	{
		int a, b;
		cin >> a >> b;
		for (int j = 0; j < n; j++)
		{
			if (map[j] == a)
			{
				for (int k = 0; k < n; k++)
				{
					if (map[k] == b)
					{
						m[j][k] = 1;
						m[k][j] = 1;
					}
				}
			}
		}
	}

	return m;
}

void printMatrix(int** m, int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = -1; j < n; j++)
		{
			if (j == -1)
				cout <<"\t" << a[i] << "\t";
			else
				cout << m[i][j] << "\t";
		}
		cout << "\n";
	}
}

void printArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}


void dijkstra(int n, bool** m, int* visited, int* tezina, int c)
{
	visited[c] = 1;
	for (int i = 0; i < n; i++)
	{
		if (m[c][i])
		{
			if ((m[c][i] + tezina[c]) < tezina[i])
			{
				tezina[i] = (m[c][i] + tezina[c]);
			}
		}
	}

	bool t = false;
	for (int i = 0; i < n; i++)
	{
		if (visited[i] == 0)
		{
			t = true;
			break;
		}
	}

	if (t)
	{
		int min = 0, minV = INT32_MAX;

		for (int i = 0; i < n; i++)
		{
			if (tezina[i] < minV && visited[i] != 1)
			{
				minV = tezina[i];
				min = i;
			}
			//cout << min << endl;
		}
		dijkstra(n, m, visited, tezina, min);
	}
}



int main()
{
	int n;
	cin >> n;
	int* map = new int[n];
	bool** m = UnesiMatricu(n, map);
	//printMatrix(m, n);
	//printArray(map, n);
	int a;
	cin >> a;
	int* d = new int[a];
	int counter = 0;

	for (int i = 0; i < a; i++)
	{
		int c;
		cin >> c;
		if (c == 1)
		{
			int u, v;
			cin >> u >> v;
			
			for (int j = 0; j < n; j++)
			{
				int t = m[u - 1][j];
				m[u - 1][j] = m[v - 1][j];
				m[v - 1][j] = t;
			}
			for (int j = 0; j < n; j++)
			{
				if (m[u-1][j] == 1)
				{
					int t = m[j][u - 1];
					m[j][u - 1] = m[j][v - 1];
					m[j][v - 1] = t;
				}
				if (m[v - 1][j] == 1)
				{
					int t = m[j][u - 1];
					m[j][u - 1] = m[j][v - 1];
					m[j][v - 1] = t;
				}
			}
		
			//printArray(map, n);
		}
		else if (c == 2)
		{
			int l, r, x;
			cin >> l >> r >> x;
			int* visited = new int[n];
			int* tezina = new int[n];
			int max = 0;
			for (int j = l; j <= r; j++)
			{
				for (int k = 0; k < n; k++)
				{
					tezina[k] = INT16_MAX;
					visited[k] = 0;
				}

				tezina[j - 1] = 0;

				dijkstra(n, m, visited, tezina, j-1);

				//cout << "\t";
				/*printArray(tezina, n);
				printMatrix(m, map, n);*/
				for (int o = 0; o < n; o++)
				{
					if (map[o] == x)
					{
						if (tezina[o] > max)
						{
							max = tezina[o];
						}
					}
				}
			}

			d[counter] = max;
			counter++;
		}
			
	}


	for (int i = 0; i < counter; i++)
	{
		cout << d[i] << endl;
	}

	return 0;
}