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?
É 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).
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:
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.
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 |
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).
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
Sim Nao Sim Sim
As operações dão origem às seguintes configurações da cidade:
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
Sim Nao Sim Sim Sim
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
Nao Sim Sim Nao Sim