#P3776. 警察局

    ID: 2979 传统题 2000ms 128MiB 尝试: 72 已通过: 11 难度: 6 上传者: 标签>CF2100提高Tarjan 强连通分量算法缩点分组背包计数 DP滚动数组Pascal 递推高精度加法高精度乘法

警察局

题目描述

很久很久以前,朕拥有着 S 国的全部领土。S 国由 nn 个城市组成,而且某些城市有道路相连。不过,由于马车相向而行是非常危险的,所以道路都修成单向的。

朕决定在 S 国的若干不同城市设置警察局。不过由于特殊经济原因,朕只能建立恰好 kk 个警察局。朕建立的警察局必须符合如下条件:

  • 从每个没有警察局的城市出发,都能达到某个有警察局的城市。
  • 任意城市一旦发生危险,总有警察局能够派出人员到达那个城市。

朕想知道一共有多少种不同的方案设置警察局(话说朕**是闲的么。。。)

输入格式

每个测试点包含多组数据。

输入数据的第一行为 CC,为数据个数。

每组数据的第一行为 n,m,kn,m,k,代表了城市的个数、道路的个数以及建设的警察局数。以后 mm 行,每行两个整数 i,ji,j,表示有一条从 ii 城市到 jj 城市的道路。输入数据没有重复道路。

输出格式

对每组数据输出一行,为建立 kk 个警察局的不同方案数。

2
3 2 2
1 2
2 3
4 4 2
1 2
2 3
3 4
3 1
1

数据规模与约定

对于 100%100\% 的数据,1≤n≤1001 \le n \le 100,1≤m≤2×1041 \le m \le 2 \times 10^4,1≤k≤n1 \le k \le n,1≤C≤1.4×1031 \le C \le 1.4 \times 10^3。