P3247 [HNOI2016] 最小公倍数

给定一张 $N$ 个顶点 $M$ 条边的无向图(顶点编号为 $1,2,\ldots,n$)，每条边上带有权值。所有权值都可以分解成 $2^a\times 3^b$ 的形式。 现在有 $q$ 个询问，每次询问给定四个参数 $u,v,a$ 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a\times 3^b$。 注意：路径可以不是简单路径。 下面是一些可能有用的定义，如果与其它地方定义不同，在本题中以下面的定义为准： 最小公倍数： $ k $ 个数 $ a_1 , a_2, \ldots, a_k $ 的最小公倍数是能被每个 $a_i$ 整除的最小正整数。 路径：顶点序列 $ P \colon P_1,P_2,\ldots,P_k $ 是一条路径，当且仅当 $k \geq 2$，且对于任意 $ 1 \leq i < k $ ，节点 $ P_i $ 和 $ P_{i+1} $ 之间都有边相连。 简单路径：如果路径 $ P \colon P_1,P_2,\ldots,P_k $ 中，对于任意 $ 1 \leq s \neq t \leq k $ 都有 $ P_s \neq P_t $ ，那么称 $P$ 为简单路径。

无

无

$1\le n,q\le 5\times 10^4$，$1\leq m\leq 10^5$，$0\leq a,b\leq 10^9$。