题目描述

给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a3^b 的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得 路径依次经过的边上的权值的最小公倍数为2^a3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义 ：最小公倍数：K个数a_{1},a_{2},…,a_{k}的最小公倍数是能被每个a_{i}整除的最小正整数。路径：路径P:P_{1},P_{2},…,P_{k}是顶 点序列，满足对于任意1<=i<k，节点P_{i}和P_{i+1}之间都有边相连。简单路径：如果路径P:P_{1},P_{2},…,P_{k}中，对于任意1 <=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。

输入格式

输入文件的第一行包含两个整数N和M，分别代表图的顶点数和边数。接下来M行，每行包含四个整数u、v、a、 b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q，代表询问数。接下来q行，每行包含四 个整数u、v、a和b，代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

输出格式

对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余 字母小写） 。

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 
No 
No 

提示

没有写明提示

题目来源

没有写明来源