KFSTB - 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
hemansh_31: 2020-05-22 18:43:09

The given graph is a Directed Acyclic Graph

dkkv0000: 2020-01-22 19:11:44

easy peasy lemon squeezy

its_himanshu: 2019-12-12 14:04:54

AC in one go....

wingman__7: 2019-10-14 16:45:19

HInt:-
1) read the question statement and conclude that its a DAG.
2) to count the total number of possibilities you need to maintain an array.
3) go from destination to source.

nishanth4298: 2019-10-09 16:25:25

If the graph is a DAG, then you cant even reach the same island again, wth!!The whole question needs to be modified

Last edit: 2019-10-09 16:26:26
sumantopal07: 2019-09-13 10:45:45

Dfs and maintain an array to store number of ways to reach destination
<snip>

Last edit: 2023-01-24 22:39:21
saurabh8522: 2019-05-05 10:47:26

@samarth1402 can u please send ur solution i followed the same approach but i am getting tle

samarth1402: 2019-03-23 13:44:46

Nice DP+bfs question.
1) Make an array(way) with s = 1 and all other isand values 0
2) Do level order traversal (bfs), with way[c] += way[p]
3) ans is way[t]

Last edit: 2019-03-23 13:45:08
jagadishsagi: 2018-06-25 04:46:56

Dfs + dp AC in one go

yogi10: 2018-01-25 14:00:23

nice problem i simply thinking to the soln using dfs with some optimization give accepted *****
dfs is appropriate tag

Last edit: 2018-01-25 14:43:39

Added by:rizwan hudda
Date:2012-09-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Kodefest 2012 IITK - Own problem