#P12805. 统计强连通

    ID: 11991 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500图论强连通分量矩阵数学构造倍增2025“钉耙编程”中国大学生算法设计暑期联赛(4)

统计强连通

统计强连通

Problem Description

给定一张 简单有向图 GG 包含编号为 1,2,3,⋯ ,n1,2,3,\cdots,n 的点。此图包含 mm 条边,编号为 1,2,3,⋯ ,m1,2,3,\cdots,m,其中第 ii(1≤i≤m1\le i\le m)条边为 ui→viu_i\to v_i。 定义有向图 G0G^0 是一张包含两个编号分别为 1,21,2 的点与一条边 1→21\to2 的图。对于整数 kk(k≥1k\ge 1),定义有向图 GkG^k 是将 Gk−1G^{k-1} 中的每一条边使用 GG 同时替换所得到的图(可见 样例解释 中的参考图)。替换时将 Gk−1G^{k-1} 中的每一条边的起点视为 GG 中编号为 11 的点,终点视为 GG 中编号为 22 的点。 具体地,对于正整数 kk,按下面的方式构造有向图 GkG^k:

  1. 首先使 GkG^k 中包含与 Gk−1G^{k-1} 相同数目的点,并给它们分配与 Gk−1G^{k-1} 相同的编号。此时 GkG^k 中不包含任何边。
  2. 对于 Gk−1G^{k-1} 中的每条有向边,轮流执行一次添加操作。
  3. 给 GkG^k 中的点重新分配连续正整数编号。 一次对 Gk−1G^{k-1} 中的有向边 u→vu\to v 的添加操作如下:
  4. 在 GkG^k 中加入 nn 个新点,并按照图 GG 的方式在这 nn 个新点之间连接 mm 条有向边。设这 nn 个新点中,与图 GG 中编号为 1,21,2 的点对应的点的编号分别是 x,yx,y。
  5. 在 GkG^k 中找到编号为 u,vu,v 的点。合并编号为 u,xu,x 的点、编号为 v,yv,y 的点。合并编号为 a,ba,b 的点时,把所有形如 b→γb\to\gamma 的边修改为 a→γa\to\gamma,把所有形如 γ→b\gamma\to b 的边修改为 γ→a\gamma\to a。由于不可能出现 a→ba\to b 与 b→ab\to a,所以不需要考虑。允许出现重边。 如果你还是不理解这个过程,可以参考 样例解释 的伪代码。 给定图 GG 和非负整数 k′k',计算 Gk′G^{k'} 中的强连通分量的个数。对 10000000071000000007 取模。

Input

本题包含多组测试数据。 首先在第一行输入一个整数 TT(1≤T≤1001\le T\le100)表示测试数据组数。 对于每一组测试数据,输入包含 m+1m+1 行。 第一行包含三个整数 n,m,k′n,m,k'(2≤n≤1052\le n\le 10^5,2≤∑n≤3×1052\le\sum n\le 3\times 10^5,0≤m≤∑m≤1060\le m\le\sum m\le10^6,0≤k′≤10180\le k'\le 10^{18}),分别表示 GG 中点与边的数量,以及与计算答案有关的参数。 接下来 mm 行,第 i+1i+1(1≤i≤m1\le i\le m)行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n)表示一条 GG 中的边 ui→viu_i\to v_i。 保证输入的点与边构成一张简单有向图。(即无重边与自环)

Output

对于每一组测试数据,输出包含一行一个整数表示 Gk′G^{k'} 中强连通分量个数对 10000000071000000007 取模后的值。

Sample Input

3
3 3 1919810
1 2
2 3
3 1
5 5 2
1 5
1 3
3 4
4 2
2 3
4 4 5
1 3
2 3
3 4
4 3

Sample Output

1
8
428

Hint

在样例的第二组测试数据中,将 G1G^1 中的每一条边使用 GG 同时替换的过程如下图所示(其中黑色虚线边表示 G1G^1 中的边 u′→v′u'\to v',这条边仅作指示作用,在 G2G^2 中不存在, 仅一部分图中绘制了黑色虚线边 ):

答案为 88。 在这里给出伪代码,伪代码以图 GG 和整数 kk 作为输入,返回图 GkG^k:

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(4)