1569_howmanypa

Given an directed graph G = (V, E), and two vertices u, v ∈ V, you are asked to determine how many deferent path between u and v.

The input begins with a line containing an integer T (T ≤ 500), which indicates the number of test cases. Each case begins with four integers N, M, u and v (2 ≤ N ≤ 10000, 0 ≤ M ≤ 100000, 1 ≤ u, v ≤ N, u ≠ v). The following M lines each consist of two integers a and b (1 ≤ a, b ≤ N, a ≠ b), indicating that arc <a, b> ∈ E.

For each case, output the number of different path from a to b .

2

4 4 1 2
1 3
3 4
4 2
2 3

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

2
0