É possível verificar se dois vértices são alcançáveis num grafo?
Você tem um grafo não direcionado com
v vértices e e arestas. É fornecido um número q de consultas em que se pede para verificar se dois vértices são alcançáveis — isto é, se existe um caminho que permita chegar de um vértice ao outro percorrendo o grafo.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 1000) e e (1 ≤ e ≤ 1000).As próximas
e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.Em seguida, há uma linha com um único inteiro
q (1 ≤ q ≤ 100), que representa o número de consultas.As
q linhas seguintes trazem pares de inteiros q1, q2 (1 ≤ q1, q2 ≤ v), que são os vértices a serem verificados.Saída
Para cada uma das
q consultas, o programa deve imprimir Yes se for possível ir do vértice q1 até q2, ou No caso contrário.Exemplos
Entrada | Saída |
7 6
1 2
2 3
1 3
4 5
5 6
4 6
4
1 2
2 5
3 6
4 6 | Yes
No
No
Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB