最短路

给定一个个节点,条有向边的图,再给你起点和终点,请问其中有多少条互不重叠的从起点到终点的最短路,即互相没有公共边的最短路个数(可以有公共点),用过边的不能再用。

输入第一行有一个,表示样例个数。
每个样例第一行有两个整数
然后是行,代表每一条边的起点终点和权值。
然后是一个两个整数,代表起点和终点。

输出最短路个数。

4
4 4
1 2 1
1 3 1
2 4 1
3 4 1
1 4
7 8
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
1 7
6 7
1 2 1
2 3 1
1 3 3
3 4 1
3 5 1
4 6 1
5 6 1
1 6
2 2
1 2 1
1 2 2
1 2

2
2
1
1