Можно ли добраться от одной вершины к другой в графе?
Вам дан неориентированный граф с
v вершинами и e рёбрами.Также имеется q запросов, в каждом из которых нужно проверить, достижимы ли две указанные вершины, то есть можно ли, двигаясь по графу, попасть из одной вершины в другую.Входные данные
Первая строка содержит два целых числа
v (1 ≤ v ≤ 1000) и e (1 ≤ e ≤ 1000).В следующих
e строках представлены пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), которые указывают, что вершина v1 соединена с вершиной v2, и наоборот.Затем в отдельной строке задаётся целое число
q (1 ≤ q ≤ 100) — количество запросов.В следующих
q строках каждая содержит по два целых числа q1, q2 (1 ≤ q1, q2 ≤ v), которые обозначают вершины, между которыми нужно проверить достижимость.Выходные данные
Для каждого запроса выведите
Yes, если из вершины q1 действительно можно добраться до вершины q2, и No в противном случае.Примеры
Входные данные | Выходные данные |
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