Problema C - Semáforos

Chegou o dia da grande final das ONI que se irá realizar no DCC! Como devem imaginar, os organizadores estão muito atarefados a tratar dos últimos pormenores. Neste momento a tarefa em mão é de transportar várias coisas (cartazes, enunciados, comida, ...) de um lado para o outro do Porto, de carro.

Felizmente, sabemos que o Porto é uma cidade com N cruzamentos e com N - 1 ruas (que ligam dois cruzamentos quaisquer) tal que todos os cruzamentos estão ligados por pelo menos um caminho (o Porto é conexo). Além disso sabemos que cada rua tem um semáforo que pode estar verde ou vermelho. Todos os semáforos começam a verde, mas com o tempo vão mudando de cor, não seguindo nenhum padrão em específico.

Para os organizadores interessa saber se é possível chegar de um dado cruzamento a outro usando apenas as ruas da cidade. Claro que não convém passar nenhum semáforo vermelho, sob pena de apanharmos uma grande multa. Assim, para chegar de um cruzamento a outro, só se podem usar ruas onde os semáforos estejam a verde.

O problema é que enquanto se vão movendo de sítio para sítio, os semáforos vão mudando e pode acontecer que já não dê para chegar a um certo cruzamento a partir de outro cruzamento. Como não queriam preocupar-se muito com isso, os organizadores decidiram que os concorrentes deviam tratar dessa questão e por isso colocaram esse problema aos concorrentes. Conseguem resolvê-lo?

O Problema

É dada a configuração das ruas do Porto sob a forma de N - 1 pares de cruzamentos (os cruzamentos estão numerados de 1 a N) que indicam o que cada rua liga. Posteriormente são dadas Q operações que podem ser de dois tipos: uma operação que troca a cor do semáforo de uma determinada rua; uma operação que pergunta se é possível chegar de um cruzamento A a um cruzamento B. A tua tarefa é ser capaz de processar uma sequência desta operações.

Para uma dada pergunta, notem que só precisam de saber se é possível chegar de um cruzamento ao outro, ou seja, os semáforos não mudarão durante essa viagem (têm de considerar o estado atual dos semáforos como fixo para responder a cada pergunta).

Input

Na primeira linha vêm um inteiro N que representa o número de cruzamentos. Seguem-se N - 1 linhas, cada uma contendo dois inteiros distintos, A e B que representam os cruzamentos que cada rua une. É garantido que não existem duas ruas que ligam os mesmos dois cruzamentos.

Na linha seguinte vem um inteiro Q, representando o número de operações a suportar. Seguem-se Q linhas contendo um dos dois seguintes formatos:

Output

Para cada operação do tipo 'P', uma linha com a palavra 'Sim' (sem aspas) caso seja possível viajar entre os cruzamentos dados, ou 'Nao' (sem aspas) caso contrário.

Restrições

São garantidos os seguintes limites em todos os casos de teste:

1 ≤ N ≤ 105       Número de cruzamentos
1 ≤ Q ≤ 105       Número de operações

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 20% dos pontos, acontece sempre que N≤20.

Para um conjunto de casos de teste valendo 45% dos pontos, acontece sempre que N≤2 000.

Para um outro conjunto de casos de teste valendo mais 30% dos pontos, as operações do tipo 'P' são sempre entre o cruzamento 1 e um outro cruzamento qualquer (o cruzamento 1 é o DCC).

Exemplo de Input 1

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

Exemplo de Output 1

Sim
Nao
Sim
Sim

Explicação do Input/Output 1

As operações dão origem às seguintes configurações da cidade:

Exemplo de Input 2

8
1 2
3 1
1 4
2 5
8 3
7 5
6 5
8
M 2 5
P 6 7
P 6 3
P 8 4
M 1 4
P 8 3
M 5 2
P 6 1

Exemplo de Output 2

Sim
Nao
Sim
Sim
Sim

Exemplo de Input 3

8
1 2
3 1
1 4
2 5
8 3
7 5
6 5
8
M 2 5
P 1 7
P 1 3
P 8 1
M 1 4
P 1 4
M 5 2
P 6 1

Exemplo de Output 3

Nao
Sim
Sim
Nao
Sim

Prova de Seleção para as IOI'2015
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(23 de Maio de 2015)