Russia and Cremia
Russia after taking over Cremia wants to have rapid development of Cremia.To make this happen Russia wants a city of Cremia to become the economic capital of new Russia with Cremia included.They also want good connectivity between Moscow,capital of Russia, and the economic capital from Cremia.
Russia along with Cremia has cities connected by only one way roads.To ensure high connectivity, two cities are sometimes directly connected by even more than one road.
Connectivity of a pair of cities is defined as the number of paths between the two cities.A road can be used in a path more than once if possible.Two paths are considered different if they do not use exactly the same sequence of roads.
There are N cities in Russia,Cremia included, and M one way roads.City 1 is Moscow and city N is the economic capital from Cremia.your task is to find the connectivity between Moscow and the economic capital,i.e how many different paths are there from city 1 to city N?
The first line of input contains the number of test cases T.
Each test case begins with two intergers N and M, deonting number of cities and number of one way roads.Next M lines of each test case contains two integers X and Y denoting a one way raod from city X to city Y.
For each test case print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9), if there are infinitely many different paths print “INFINITE PATHS”(quotes are for clarity).Answer of each test case must be in separate line.
0 < T <= 20
1 < N <=10000
0 < M <= 10^5
0 < X <= N
0 < Y <= N
Problem Setter : Akshay Kumar