KFSTB  Help the Commander in Chief
Help the Commander in Chief
The Country of byteland is in a state of war with its neighboring nation bitland which is a small island. The king of byteland needs to send his soldiers across the sea to attack bitland. It is not easy for bytelandian soldiers to cross the sea between the two countries as there are soldiers of bitland who are constantly on patrol.
But, The commander of byteland through his secret sources has gathered some information about the camping spots in between, It is as follows. There are C camping spots in the sea between the two countries. There are B one way bridges, each bridge is between two camps. Bytelandian army can use these bridges without any danger of being attacked. The commander also knows that if the army leaves a camping spot along a bridge safely it is not possible to return back safely to the same camping spot.
The camping spot closest to the bytelandian shore is S and the camping spot closest to the bitlandian shore is T. The commander in chief of byteland wants to formulate a strategy for the army to safely move from the camping spot S to T. You have been assigned the task of finding the number of possible paths that a soldier could follow from camping spot S to T.
Input
The first line of input contains the number of test cases D. For each test case the first line contains C, B, S and T number of camping spots, number of one way bridges, camping spot close to byteland and camping spot close to bitland respectively. The next B lines contain description of bridges. Each bridge is described on a single line by two integers X and Y denoting the starting and ending point of a bridge.
Output
In each line print the number of possible paths modulo 1000000007
Sample Input
2
4 4 1 4
1 2
1 3
2 4
3 4
5 5 1 5
1 2
2 3
2 4
3 5
4 5
Sample Output
2
2
Constraints
1<= D <= 10
1<= C <= 10000
1<= B <= 10000
1 <= X,Y <= C
1 <= S,T <= C
hide comments
samarth1402:
20190323 13:44:46
Nice DP+bfs question.


jagadishsagi:
20180625 04:46:56
Dfs + dp AC in one go 

yogi10:
20180125 14:00:23
nice problem i simply thinking to the soln using dfs with some optimization give accepted *****


sandeepd:
20161013 20:20:26
The #dfs tag for this problem is almost misleading! It is actually memoization + general intuition! :P Last edit: 20161013 20:22:40 

Ram:
20160404 19:50:05
In python if you are getting NZEC error, try to increase recursion limit (for DP topdown). 

Praveen Gajulapalli:
20160309 20:33:08
Problem description should say that the graph is a DAG 

aditya730:
20160121 12:19:45
Think the problem description could've conveyed that the graph will be a DAG.That's crucial for solving this problem 

Projjal Kundu:
20151214 15:58:38
Reverse Topological sort + DP 

Deeksha:
20150628 18:45:09
Using dfs.. but i keep getting TLE :(


Shivam Pahuja:
20150521 07:49:03
Combination of DFS and DP can solve the problem , Don't forget to consider corner case when source is same as destination :) 
Added by:  rizwan hudda 
Date:  20120904 
Time limit:  0.714s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Kodefest 2012 IITK  Own problem 