#T2320. 禁入城市(Forbidden Cities)

禁入城市(Forbidden Cities)

链接: https://cses.fi/problemset/task/1705

板块: Advanced Graph Problems

时限: 1.00 s | 内存: 512 MB

题目描述

有 nn 座城市和 mm 条它们之间的道路。Kaaleppi 目前在城市 aa,想去城市 bb。

但有一个问题:Kaaleppi 最近在城市 cc 抢了银行,不能进入该城市,否则当地警察会抓住他。你的任务是判断是否存在一条从城市 aa 到城市 bb、且途中不经过城市 cc 的路线。

作为额外的挑战,你需要处理 qq 组查询,其中 aa、bb 和 cc 会变化。

输入

第一行包含三个整数 nn、mm 和 qq:城市数量、道路数量和查询数量。城市编号为 1,2,…,n1,2,\dots,n。

接下来有 mm 行描述道路。每行包含两个整数 aa 和 bb:表示城市 aa 与 bb 之间有一条道路。每条道路都是双向的。

最后有 qq 行描述查询。每行包含三个整数 aa、bb 和 cc:是否存在一条从城市 aa 到城市 bb 且不经过城市 cc 的路线?

你可以假定任意两座城市之间都存在路线。

输出

对于每组查询,如果存在这样的路线,输出 "YES",否则输出 "NO"。

数据范围

1≤n≤1051 \le n \le 10^5 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5 1≤q≤1051 \le q \le 10^5 1≤a,b,c≤n1 \le a,b,c \le n

样例输入

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