#1369 Too Many Ways to Go

64  1 s   128 MB  

Description

정점이 N 개, 간선이 M 개 있는 사이클을 포함하지 않는 무방향 그래프 G가 있다.

이 그래프의 임의의 두 정점 S와 E 사이의 최단 경로의 개수를 구하여라.

Input

입력은 여러 개의 테스트 케이스로 구성된다. 첫 행에는 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 행에는 N (1 <= N <= 10000) 과 M, S, E (S != E) 가 주어진다.

다음 M 행에 걸쳐 각 간선의 양 끝 점의 인덱스가 주어진다.

주어진 모든 인덱스는 0부터 세며, 중복된 간선은 주어지지 않는다.

Output

각 테스트 케이스에 대해 한 행에 하나씩 경우의 수를 1000000003 으로 나눈 나머지를 출력한다.

Sample Input

Sample Output

1
3 2 0 2
0 1
1 2
1