#Q. 「HNOI2016」最小公倍数

    Type: Default 8000ms 256MiB

「HNOI2016」最小公倍数

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一张 N N 个顶点 M M 条边的无向图(顶点编号为 1,2,,n 1,2, \cdots ,n ),每条边上带有权值。所有权值都可以分解成 2a3b 2^a \cdot 3^b 的形式。

现在有 q q 个询问,每次询问给定四个参数 u u v v a a b b ,请你求出是否存在一条顶点 u u v v 之间的路径,使得路径依次经过的边上的权值的最小公倍数为 2a3b 2^a \cdot 3^b

注意:路径可以不是简单路径。

下面是一些可能有用的定义:
最小公倍数: k k 个数 a1,a2,,ak a_1 , a_2, \cdots , a_k 的最小公倍数是能被每个 aia_i 整除的最小正整数。
路径:路径 P ⁣:P1,P2,,Pk P \colon P_1,P_2,…,P_k 是顶点序列,满足对于任意 1i<k 1 \leq i < k ,节点 Pi P_i Pi+1 P_{i+1} 之间都有边相连。
简单路径:如果路径 P ⁣:P1,P2,,Pk P \colon P_1,P_2,…,P_k 中,对于任意 1stk 1 \leq s \neq t \leq k 都有 PsPt P_s \neq P_t ,那么称路径为简单路径。

输入格式

输入文件的第一行包含两个整数 N N M M ,分别代表图的顶点数和边数。
接下来 M M 行,每行包含四个整数 u u v v a a b b 代表一条顶点 u u v v 之间、权值为 2a3b 2^a \cdot 3^b 的边。
接下来一行包含一个整数 q q ,代表询问数。
接下来 q q 行,每行包含四个整数 u u v v a a b b ,代表一次询问。
询问内容请参见问题描述。

输出格式

对于每次询问,如果存在满足条件的路径,则输出一行 Yes,否则输出一行 No

注意:第一个字母大写,其余字母小写) 。

样例

4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4
Yes
Yes
Yes
No
No

数据范围与提示

对于所有的数据,$1 \leq n,q \leq 50000,\ 1 \leq m \leq 100000,\ 0 \leq a,b \leq 10^9 $。

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45