[Hnoi2016]最小公倍数

时间限制:40s      空间限制:512MB

题目描述

  给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n),每条边上带有权值。所有权值都可以分解成2^a*3^b
的形式。现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得
路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意:路径可以不是简单路径。下面是一些可能有用的定义
:最小公倍数:K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径:路径P:P1,P2,…,Pk是顶
点序列,满足对于任意1<=i<k,节点Pi和Pi+1之间都有边相连。简单路径:如果路径P:P1,P2,…,Pk中,对于任意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(注意:第一个字母大写,其余
字母小写) 。


样例输入

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 

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose