#P18184. Sheriruth

Sheriruth

Sheriruth

给定一个简单有向图 G=(V,E)G=(V,E),其中 V={0,1,…,n−1}V=\{0,1,\ldots,n-1\},初始有 mm 条边。

若三个顶点 a,b,c∈Va,b,c\in V 满足以下全部条件:

  • b≠cb\ne c;
  • 存在边 a→ba\to b;
  • 存在边 a→ca\to c;
  • 尚不存在边 b→cb\to c;

就向图中加入边 b→cb\to c。反复执行这种操作,直到再也无法加入新边。可以证明,最终得到的图 G′=(V,E′)G'=(V,E') 唯一,与操作顺序无关。

接下来回答 qq 次询问。每次给出两个顶点 u,vu,v,求最终图 G′G' 中从 uu 到 vv、沿途不重复经过任何顶点的有向路径数量。答案对 SS 取模。

当 u=vu=v 时,只计长度为 00 的空路径,答案为 1 mod S1\bmod S;绕环返回起点会重复经过该顶点,不计入答案。

输入格式

第一行四个整数 n,m,q,Sn,m,q,S。

接下来 mm 行,每行两个整数 u,vu,v,表示初始图中的一条有向边 u→vu\to v。

接下来 qq 行,每行两个整数 u,vu,v,表示一次询问。

输出格式

输出 qq 行,每行一个整数,依次表示对应询问的答案对 SS 取模的结果。

数据范围

  • 1≤n≤5×1051\le n\le 5\times10^5;
  • 0≤m≤1060\le m\le 10^6;
  • 1≤q≤1061\le q\le 10^6;
  • 1≤S≤2301\le S\le 2^{30},不保证 SS 为素数;
  • 所有顶点编号均属于 [0,n−1][0,n-1];
  • 初始边的两端不同,且没有同向重边;反向的两条边可以同时存在;
  • 图不保证连通,可以有孤立点;询问允许 u=vu=v。

样例输入

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