O Chefe

Todos conhecem Iks, a última moda em redes sociais, que fez tanto sucesso que competidores como Facebook e Google+ estão começando a ter dificuldades financeiras. Assim como muitas companhias ".com", Iks surgiu em uma pequena garagem, mas hoje emprega milhares de pessoas no mundo todo.

O sistema de gerência utilizado em Iks é bem diferente do padrão. Por exemplo, não há diretorias ou superintendências. No entanto, como é usual em outras companhias, há uma cadeia (ou melhor, várias cadeias) de comando: uma pessoa pode gerenciar outras pessoas, e pode ser gerenciada por outras pessoas. As figuras abaixo mostram a cadeia de comando para alguns empregados, junto com suas idades.

Uma pessoa P₁ pode gerenciar outra pessoa P₂ diretamente (quando P₁ é o superior imediato de P₂) ou indiretamente (quando P₁ gerencia diretamente uma pessoa P₃ que gerencia P₂ direta ou indiretamente). Por exemplo, na figura (a) acima, Alice gerencia David diretamente e Clara indiretamente. Uma pessoa não gerencia a si própria, nem direta nem indiretamente.

Um folclore que apareceu em Wall Street é que Iks é tão bem sucedido porque em sua rede de comando um(a) gerente é sempre mais jovem do que as pessoas que ele(a) gerencia. Como podemos ver na figura acima, isso não é verdade. Mas esse folclore incentivou Iks a desenvolver uma ferramenta para analisar o seu sistema de gerenciamento, e estudar se tem alguma influência no sucesso da empresa. Você foi contratado para trabalhar nessa ferramenta.

Dadas a descrição da cadeia de comando na Iks e as idades de seus empregados, escreva um programa que execute uma série de instruções. Instruções podem ser de dois tipos: trocas de gerência e perguntas. Uma instrução de troca de gerência faz dois empregados A e B trocarem suas posições na cadeia de comando. Como exemplo, a figura (b) acima mostra a cadeia de comando resultante quando David e George trocam suas respectivas posições na cadeia de comando. Uma instrução de pergunta identifica um empregado A e deseja saber a idade do mais jovem gerente (direto ou indireto) de A na cadeia de comando. Por exemplo, no cenário da figura (a) acima a idade do(a) gerente mais jovem de Clara é 18 anos; já no cenário da figura (b), a idade do(a) gerente mais jovem de Clara é 21 anos.

Entrada

Cada uma das M linhas seguintes contém dois inteiros X e Y, indicando que X gerencia Y diretamente. Seguem-se I linhas, cada uma descrevendo uma instrução. Uma instrução de troca de gerência é descrita em uma linha contendo o identificador T seguido de dois inteiros A e B, indicando os dois empregados que devem trocar seus lugares na cadeia de comando. Uma instrução de pergunta é descrita em uma linha contendo o identificador P seguido de um inteiro E , indicando um empregado. A última instrução será sempre do tipo pergunta.

Saída

Restrições

• 1 ≤ N ≤ 500
• 0 ≤ M ≤ 60 \times 10³
• 1 ≤ I ≤ 500
• 1 ≤ K_i ≤ 100, para 1 ≤ i ≤ N
• 1 ≤ X,Y ≤ N, X ≠ Y
• 1 ≤ A,B ≤ N
• 1 ≤ E ≤ N

Exemplos

7 8 9
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
P 7
T 4 2
P 7
P 5
T 1 4
P 7
T 4 7
P 2
P 6

18
21
18
18
*
26
	

6 5 6
10 20 30 40 50 60
1 5
1 4
3 6
2 5
4 5
P 1
P 5
P 6
T 1 6
P 1
P 4

*
10
30
30
60