Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HEDGE11 - Labirintos de Cerca Viva

A Rainha da Nlogônia é uma fã de labirintos, e então os arquitetos do reino construiram vários labirintos em volta do palácio da Rainha. Todo labirinto construido para a Rainha é feito de salas conectadas por corredores. Cada corredor conecta um par diferente de salas distinta e pode ser atravessado em ambas as direções.

A Rainha ama passear pelas salas e corredores do labirinto nos finais de tarde. Seus serventes escolhem um desafio diferente todo dia, que consiste em encontrar um caminho simples de uma sala inicial até uma sala final no labirinto. Um caminho simples é uma sequência de salas distintas tal que cada par de salas consecutivas é conectado por um corredor. Neste caso a primeira sala da sequência deve ser a sala inicial, e a última sala deve ser a sala final. A Rainha acha que um desafio é bom quando, dentre as rotas da sala inicial até a sala final, exatamente uma delas é um caminho simples. Você pode ajudar os serventes da Rainha a escolher um desafio que agrada a Rainha?

Para tal, escreva um programa que dados a descrição de um labirinto e uma lista de consultas definindo a sala inicial e a sala final, determina para cada consulta se aquela escolha é um bom desafio ou não.

Entrada

Cada caso de teste é descrito usando várias linhas. A primeira linha contém três inteiros R, C e Q representando respectivamente o número de salas do labirinto (2 ≤ R ≤ 104), o número de corredores (1 ≤ C ≤ 105), e o número de consultas (1 ≤ Q ≤ 1000). As salas são identificadas por inteiros de 1 até R. Cada uma das próximas C linhas descreve um corredor usando dois inteiros distintos A e B, indicando que existe um corredor conectando as salas A e B (1 ≤ A,B ≤ R). Após isso, cada uma das próximas Q linhas descreve uma consulta usando dois inteiros distintos S e T indicando respectivamente as salas inicial e final do desafio (1 ≤ S,T ≤ R). Você pode assumir que em cada caso de teste existe no máximo um corredor conectando cada par de salas, e não haverá duas consultas iguais.

O último caso de teste será seguido por uma linha contendo três zeros.

Saída

Para cada caso de teste imprima Q+1 linhas. Na i-ésima linha escreva a resposta para a i-ésima consulta. Se as salas formam um bom desafio, então escreva o caractere 'Y' (maiúsculo). Caso contrário escreva o caractere 'N' (maiúsculo). Imprima uma linha contendo um único caractere '-' (hífen) depois de cada caso de teste.

Exemplo

Entrada

6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
4 2 3
1 2
2 3
1 4
1 3
1 2
0 0 0

Saida

Y
N
N
-
N
Y
Y
-


Adicionado por:Wanderley Guimarăes
Data:2012-05-27
Tempo limite:1.919s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programaçăo da ACM 2011

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.