#P1098. 「HNOI2016」最小公倍数

    ID: 102 Type: Default 8000ms 256MiB Tried: 2 Accepted: 1 Difficulty: 10 Uploaded By: Tags>数据结构并查集2016离线HNOI分块及按大小分类

「HNOI2016」最小公倍数

题目描述

给定一张 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 $。