#3776. 警察局

题目描述

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

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

1、从每个没有警察局的城市出发，都能达到某个有警察局的城市。

2、任意城市一旦发生危险，总有警察局能够派出人员到达那个城市。

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

输入格式

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

输入数据的第一行为C，为数据个数。

每组数据的第一行为N、M和K，代表了城市的个数、道路的个数以及建设的警察局数。以后M行，每行两个整数i、j，表示有一条从i城市到j城市的道路。输入数据没有重复道路。

输出格式

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

样例

样例输入

2  

3 2 2  

1 2  

2 3  

4 4 2  

1 2  

2 3  

3 4  

3 1  

样例输出

1  

数据范围与提示

对于100%的数据，有1<=N<=100，1<=M<=20000，1<=K<=N，1<=C<=1400

Notice:此题从前那个加重复了，因而换成现在这个题，不好意思，浪费大家的提交了。