Forbidden Cities

题目描述

有 n 个城市和 m 条连接它们的道路。Kaaleppi 目前在城市 a，想要前往城市 b。 然而，有一个问题：Kaaleppi 最近在城市 c 抢劫了银行，不能进入该城市，因为当地警察会抓住他。你的任务是确定是否存在一条从城市 a 到城市 b 的路径，该路径不经过城市 c。 作为额外的挑战，你需要处理 q 个查询，其中 a、b 和 c 会变化。

输入格式

第一行包含三个整数 n、m 和 q：城市数、道路数和查询数。城市编号为 1,2,$\dots$,n。 接着有 m 行描述道路。每行包含两个整数 a 和 b：表示城市 a 和 b 之间有一条道路。每条道路是双向的。 最后有 q 行描述查询。每行包含三个整数 a、b 和 c：是否存在一条从城市 a 到城市 b 的路径，该路径不经过城市 c？ 你可以假设任意两座城市之间都存在一条路径。

输出格式

对于每个查询，若存在这样的路径则输出 "YES"，否则输出 "NO"。

5 6 3
1 2
1 3
2 3
2 4
3 4
4 5
1 4 2
3 5 4
3 5 2

YES
NO
YES

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le q \le 10^5$ $1 \le a,b,c \le n$

标签: CSES1705|高级图论问题

来源

CSES1705|高级图论问题