4. Отбой

Задача

Определите, сможет ли Петя гарантированно добраться между парами домиков, если при тревоге часть дорожек становится недоступной.

Входные данные

В первой строке заданы целые числа $n$, $m$ и $t$ ($3 \leqslant n, m \leqslant 10^5$, $1 \leqslant t \leqslant n$) — количество домиков, количество дорожек и номер домика, где живёт Денис Павлович. Далее следуют $m$ строк с парами $a_i$, $b_i$ ($1 \leqslant a_i, b_i \leqslant n$) — дорожки. Затем задано число $k$ ($1 \leqslant k \leqslant 10^5$) — количество запросов. Для каждого запроса указаны домики $u_i$ и $v_i$ ($1 \leqslant u_i, v_i \leqslant n$, $u_i \ne v_i$). Известно, что Денис Павлович не живёт ни в $u_i$, ни в $v_i$.

Выходные данные

Для каждого запроса выведите Yes, если Петя не сможет гарантированно добраться незамеченным, и No иначе.

Пример

стандартный ввод      стандартный вывод
4 3 3                 Yes
4 3                   No
4 2
3 1
2
2 4
1 4

Ограничения

  • Время: 2 секунды
  • Память: 256 мегабайт
Редакционный разбор Петя теряет контроль только в одном случае: он проходит через домик $t$. Тогда преподаватели перекрывают произвольные $\lfloor m/2 \rfloor$ дорожек, и Петя не может знать, какие именно. Значит, единственная гарантия — выбрать маршрут, который полностью избегает вершину $t$. Поэтому задача сводится к проверке, лежат ли $u_i$ и $v_i$ в одной компоненте связности графа без вершины $t$. Строим граф, удаляем $t$ (просто не добавляем его в обход) и запускаем DFS/BFS. Получаем номер компоненты для каждой вершины. Для запроса отвечаем «Yes», если номера компонент различаются (значит, путь без $t$ отсутствует и Петя гарантированно попадёт в поле зрения) и «No» иначе. Предобработка выполняется за $O(n + m)$. Ответы на запросы — по $O(1)$.

Mentioned by