¿Se pueden alcanzar dos vértices en un grafo?
Se te proporciona un grafo no dirigido con
v vértices y e aristas. Hay q consultas en las que se te pide verificar si dos vértices son alcanzables, es decir, si es posible pasar de un vértice a otro recorriendo el grafo.Entrada
La primera línea de la entrada contiene dos enteros
v (1 ≤ v ≤ 1000) y e (1 ≤ e ≤ 1000).Las siguientes
e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v), lo que significa que el vértice v1 está conectado con el vértice v2 y viceversa.La siguiente línea contiene un único entero
q (1 ≤ q ≤ 100), que indica el número de consultas.Las siguientes
q líneas contienen pares de enteros q1, q2 (1 ≤ q1, q2 ≤ v), correspondientes a los vértices cuya conexión deseas comprobar.Salida
Para cada una de las consultas, el programa debe imprimir
Yes si es posible llegar del vértice q1 al vértice q2, y No en caso contrario.Ejemplos
Entrada | Salida |
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