9530 - 通讯网破坏

由于争夺资源引起的矛盾冲突,A 国和 B 国进入了战争一触即发的状态。现在 A 国的间谍机构设法得到了 B 国的通讯网络布置情况,其中每个城市可以看作一个点,在某些点之间有无向边,表示这些城市之间可以进行双向的直接通讯。A 国打算先发制人,通过核武器毁灭某个中间城市 M,一举切断B国某两个重要城市 S , T 之间的联系,即从图中删除掉 M 点之后,ST 变得不连通。但是由于 B 国的防御力量也很强大,这样的核打击只能成功进行一次且只能毁灭一个城市。

现在 A 国的首脑提出了很多种作战策略,作为 A 国的首席计算机科学家,你的任务是编写一个程序决定这些策略可行与否。

输入

输入文件的第一行为两个整数 NM,表示 B 国的城市数和可以直接通讯的城市对数目。接下来的 M 行,每行包括两个整数 C_iD_i1\leq C_i,D_i \leq NC_i \neq D_i,表示城市 C_iD_i 之间可以直接通讯。输入数据保证每对 (C_i,D_i) 最多出现一次。

接下来一行是一个整数 Q,表示 A 国首脑作出的策略数。接下来的 Q 行,每行包括三个整数 S_i,T_i,M_i1 \leq S_i,T_i,M_i\leq N,且 M_i,S_i,T_i 三个数互不相等)表示这个策略的内容是通过毁灭 M_i 来切断 S_iT_i 之间的联系。

输出

输出 Q 行,表示对应的策略可行与否。如果毁灭 M_i 以后,S_iT_i 之间不能通讯,说明此策略可行,则应在第 i 行输出 \mathtt{yes},否则输出 \mathtt{no}

样例

输入

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

输出

yes
no
no

提示

对于 100\% 的数据,1 \leq N \leq 20000,1\leq M\leq 100000,1 \leq Q \leq 100000

输入数据保证原图的任意两点是连通的。

来源

天津省选

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题