基于互质规则构造无向图的多组两点最短距离求解

时间限制：1.0 s 内存限制：512.0 MB

题目描述

给定正整数p, q以及常数N = 10^8。现在构建一张包含N个结点的带权无向图，结点依次以1, 2, ..., N编号。对于任意满足1 ≤ u < v ≤ N的u, v，向图中加入一条连接结点u与结点v的无向边，边权规则如下：

• 若u, v互质（最大公因数为1），边权为p
• 否则边权为q

现在给定n组询问，第i组询问给定两个正整数a_i, b_i，你需要回答结点a_i与结点b_i之间的最短距离。

输入格式

第一行三个正整数n, p, q，分别表示询问数量、互质边权、非互质边权。 接下来n行，每行两个正整数a_i, b_i，表示一组询问。

输出格式

输出共n行，每行一个整数，表示对应询问的最短距离。

样例

输入样例1

4 4 3
1 2
2 3
4 2
3 5

输出样例1

4
4
3
4

输入样例2

6 2 6
1 2
2 3
4 2
3 5
6 6

输出样例2

2
2
2
4
2
0

数据范围

• 对于30%的测试点：1 ≤ n ≤ 10，1 ≤ a_i, b_i ≤ 50
• 对于另外30%的测试点：1 ≤ a_i, b_i ≤ 250
• 对于所有测试点：1 ≤ n ≤ 10^4，1 ≤ a_i, b_i ≤ 10^9，1 ≤ p, q ≤ 10^9