Sind zwei Knoten in einem Graphen erreichbar?
Sie haben einen ungerichteten Graphen mit
v Knoten und e Kanten. Zusätzlich gibt es q Anfragen, bei denen überprüft werden soll, ob man von einem Knoten zum anderen gelangen kann, indem man den Graphen durchläuft.Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
v (1 ≤ v ≤ 1000) und e (1 ≤ e ≤ 1000).Die folgenden
e Zeilen enthalten jeweils zwei Ganzzahlen v1, v2 (1 ≤ v1, v2 ≤ v), was bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist (und umgekehrt).Die nächste Zeile enthält eine einzige Ganzzahl
q (1 ≤ q ≤ 100), die angibt, wie viele Anfragen gestellt werden.In den darauffolgenden
q Zeilen befinden sich jeweils zwei Ganzzahlen q1, q2 (1 ≤ q1, q2 ≤ v), bei denen geprüft werden soll, ob eine Verbindung zwischen q1 und q2 möglich ist.Ausgabe
Für jede dieser Anfragen soll das Programm
Yes ausgeben, wenn der Knoten q1 von q2 (oder umgekehrt) aus erreichbar ist. Andernfalls wird No ausgegeben.Beispiele
Eingabe | Ausgabe |
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