Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2699
Police Cities

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Once upon the time there lived a king and he had a big kingdom. And there were n cities in his kingdom and some of them were connected by the roads. And the roads were all one-way because it would be dangerous if two carriages riding in opposite directions met on a road.

And once the king decided that he would like to establish police in his country and ordered to build police stations in some cities. But since his finances are limited, he would only like build police stations in k different cities. He would like to build them in such a way, that the following conditions were satisfied:

  • it is possible to get by the roads from each city to some city with the police station;
  • it is possible to get by the roads to each city from some city with the police station.

Now the king wants to know how many different ways are there to do so. Help him to find the answer to this question.


There are mutilple cases in the input file.

The first line of each case contains n , m and k --- the number of cities and roads in the kingdom, and the number of police stations to build, respectively (1 <= n <= 100 , 0 <= m <= 20,000 , 1 <= k <= n ). The following m lines contain two city numbers each and describe roads, remember that it is only possible to travel along roads in one direction --- from the first city to the second one. Two cities may be connected by more than one road.

There is an empty line after each case.


Output the only integer number --- the number of ways to fulfil king's request.

There should be an empty line after each case.

Sample Input

6 7 3
1 2
2 3
3 1
3 4
4 5
5 6
6 5

Sample Output


Source: Andrew Stankevich's Contest #9
Submit    Status