favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Graph decompositions

One day Zhomart was solving a path routing problem related to networks. He discovered that his underlying graph is directed and acyclic. When Serik came to see this problem he was wonder that there are many ways to decompose Zhomart’s graph into edge-disjoint paths. Friends now started to think in how many ways this can be done. Please help them.


First line contains two integers n and m (1n1000, 1m499500). Each of the next m lines contains two integers i, j meaning that there is a directed edge from vertex i to vertex j in the given graph.


Output one integer number – the answer to the problem by modulo 109 + 7.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
3 3
1 2
2 3
1 3
Output example #1
Source 2014 KBTU Open, Spring Kazakhstan, Almaty, April, 20, Problem F