Problema C - Circuitos elétricos

Como trabalho de casa de Física, o Marco tem a tarefa chata de analisar um circuito elétrico especial. Especial porque este circuito é feito de circuitos mais pequenos que se juntam usando duas regras em particular. Cada circuito tem um único terminal positivo e um único terminal negativo.

O circuito mais simples que existe é apenas uma pilha, como mostra a imagem seguinte.

Tendo dois quaisquer circuitos, podemos juntá-los e formar um novo circuito de duas formas. A primeira forma é ligá-los em série, ou seja, colocar um fio entre o terminal negativo do primeiro circuito e o terminal positivo do segundo circuito. Esta situação é representada na imagem seguinte.

A segunda forma é ligá-los em paralelo, ou seja, ligar um pequeno conetor aos terminais positivos de cada um dos circuitos e um novo pequeno conetor aos terminais negativos de cada um dos circuitos. Esta situação é representada na imagem seguinte.

Dadas estas regras de construção de um circuito, podemos descrever um qualquer circuito através de uma lista com N instruções. Vamos considerar 3 instruções (uma para cada regra): a instrução 'U', que representa uma pilha; a instrução 'S a b' que liga os circuitos 'a' e 'b' (ou seja, os circuitos definidos nas linhas 'a' e 'b' da lista de instruções) em série (por esta ordem); a instrução 'P a b' que liga os circuitos 'a' e 'b' em paralelo. Vamos ver um exemplo:

U
U
S 1 2
U
P 3 4

O circuito final é representado pela última linha das instruções ('P 3 4'), que nos indica que temos de ligar em paralelo os circuitos definidos nas linhas 3 ('S 1 2') e 4 ('U'). Por sua vez o circuito na linha 3 indica-nos que temos de ligar os circuitos nas linhas 1 ('U') e 2 ('U') em série. O circuito final está representado na imagem seguinte, onde os números indicam as linhas das instruções a que se referem.

A descrição do circuito do trabalho de casa do Marco é fornecida como uma lista de instruções como a descrita acima. Para o analisar o Marco tem de calcular a "resistência" entre alguns pares de pilhas (nota: a definição de resistência neste problema é diferente da noção física que um circuito real possui). Definimos a resistência entre duas pilhas como o número mínimo de fios diferentes que é necessário atravessar para chegar de uma pilha à outra (os fios podem ser atravessados em ambas as direções). Por exemplo, a resistência entre a pilha 1 e 2 é de 1, visto que podemos seguir o fio entre elas (representado por uma linha de pontos vermelha na imagem seguinte). Já entre as pilhas 2 e 4 a resistência é de 2, visto que temos de seguir um fio desde a pilha 2 até ao conetor da direita e outro desde esse conetor até à pilha 4 (representado por uma linha de traços azul na imagem seguinte).

Para simplificar o trabalho de casa, o professor do Marco garantiu-lhe que o circuito respeita uma condição simples. A profundidade de uma pilha é dada pelo número de instruções que é necessário atravessar até chegar à última instrução. Podemos atravessar da instrução 'a' para a instrução 'b' se a instrução 'b' definir um circuito que liga 'a' com outro circuito. Por exemplo, as pilhas 1 e 2, no exemplo acima, têm profundidade 2, pois é necessário passar pela instrução 3 para chegar à 5, e a pilha 4 tem profundidade 1. O circuito que o Marco tem de analisar tem uma profundidade máxima de 30.

O Marco tem agora uma lista de Q pares de pilhas (dados pela linha na lista de instruções em que foram definidas) e precisa da tua ajuda para calcular a resistência entre cada uma!

O Problema

Dado um conjunto de N instruções que descrevem um circuito e um conjunto de Q pares de pilhas, calcular a resistência entre cada par.

Input

A primeira linha contém dois inteiros, N, representando o número de instruções, e Q, representando o número de pares de pilhas.

Seguem-se N linhas, num dos seguintes 3 formatos:

• 'U', representando uma pilha;
• 'S a b', representando uma ligação em série entre os circuitos definidos nas linhas a e b;
• 'P a b', representando uma ligação em paralelo entre os circuitos definidos nas linhas a e b;

Seguem-se Q linhas contendo cada uma dois inteiros, representando as linhas em que foram definidas as pilhas para as quais se deve calcular a resistência.

O circuito final está representado na última linha. É garantido que as instruções representam um circuito válido e que não há 'circuitos livres', ou seja, o circuito definido na última linha contém todos os restantes circuitos. Adicionalmente, todos os pares definidos nas últimas Q linhas representam linhas que definem uma pilha. Finalmente, o circuito dado tem profundidade no máximo 30.

Output

O output deve conter Q linhas, cada uma representando a resistência entre um par de pilhas, pela ordem dada no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Input do Exemplo 1

5 2
U
U
S 1 2
U
P 3 4
1 2
4 2

Output do Exemplo 1

1
2

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

7 3
U
U
S 1 2
U
S 4 3
U
S 5 6
1 6
4 2
6 4

Output do Exemplo 2

2
2
3

Explicação do Exemplo 2

O circuito deste exemplo é o seguinte:

Input do Exemplo 3

7 4
U
U
U
U
P 1 2
P 3 4
P 6 5
1 2
1 3
2 3
3 4

Output do Exemplo 3

2
4
4
2

Explicação do Exemplo 3

O circuito deste exemplo é o seguinte: