Due vertici sono raggiungibili in un grafo?
Ti viene fornito un grafo non orientato con
v vertici e e archi. Ci sono q interrogazioni (query) che richiedono di stabilire se due vertici sono raggiungibili, ossia se è possibile spostarsi da un vertice all’altro attraversando il grafo.Input
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 1000) ed e (1 ≤ e ≤ 1000).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v), il che significa che il vertice v1 è collegato al vertice v2 e viceversa.La riga seguente contiene un singolo intero
q (1 ≤ q ≤ 100), il numero di interrogazioni.Le successive
q righe contengono coppie di interi q1, q2 (1 ≤ q1, q2 ≤ v) che indicano i vertici oggetto delle query.Output
Per ciascuna interrogazione, il programma deve stampare
Yes se è possibile raggiungere il vertice q2 a partire da q1, oppure No in caso contrario.Esempi
Ingresso | Uscita |
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