문제1369--Too Many Ways to Go

1369: Too Many Ways to Go

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 318  통과: 88
[제출] [채점기록] [묻고답하기]

문제 설명

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

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

입력 설명

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

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

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

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

출력 설명

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

입력 예시 Copy

1
3 2 0 2
0 1
1 2

출력 예시 Copy

1

출처/분류