#P18184. Sheriruth
Sheriruth
Sheriruth
给定一个简单有向图 ,其中 ,初始有 条边。
若三个顶点 满足以下全部条件:
- ;
- 存在边 ;
- 存在边 ;
- 尚不存在边 ;
就向图中加入边 。反复执行这种操作,直到再也无法加入新边。可以证明,最终得到的图 唯一,与操作顺序无关。
接下来回答 次询问。每次给出两个顶点 ,求最终图 中从 到 、沿途不重复经过任何顶点的有向路径数量。答案对 取模。
当 时,只计长度为 的空路径,答案为 ;绕环返回起点会重复经过该顶点,不计入答案。
输入格式
第一行四个整数 。
接下来 行,每行两个整数 ,表示初始图中的一条有向边 。
接下来 行,每行两个整数 ,表示一次询问。
输出格式
输出 行,每行一个整数,依次表示对应询问的答案对 取模的结果。
数据范围
- ;
- ;
- ;
- ,不保证 为素数;
- 所有顶点编号均属于 ;
- 初始边的两端不同,且没有同向重边;反向的两条边可以同时存在;
- 图不保证连通,可以有孤立点;询问允许 。
样例输入
11 9 30 998244353
0 1
0 2
3 4
5 4
6 5
7 8
8 9
9 8
10 9
0 1
0 2
1 0
1 2
2 0
2 1
3 4
3 5
3 6
4 3
4 5
4 6
5 3
5 4
5 6
6 3
6 4
6 5
7 8
7 9
7 10
8 7
8 9
8 10
9 7
9 8
9 10
10 7
10 8
10 9
样例输出
2
2
0
1
0
1
1
0
0
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
0
1
0
0
1
1