문제
정점이 N 개, 간선이 M 개 있는 사이클을 포함하지 않는 무방향 그래프 G가 있다. 이 그래프의 임의의 두 정점 S와 E 사이의 최단 경로의 개수를 구하여라.
입력
입력의 첫 행에는 N (1≤N≤10,000) 과 M, S, E (S != E) 가 주어진다. 다음 M 행에 걸쳐 각 간선의 양 끝 점의 인덱스가 주어진다. 주어진 모든 인덱스는 0부터 세며, 중복된 간선은 주어지지 않는다.
출력
각 테스트 케이스에 대해 한 행에 하나씩 경우의 수를 1,000,000,003 으로 나눈 나머지를 출력한다.
예제
3 2 0 2
0 1
1 2
1
로그인해야 코드를 작성할 수 있어요.