시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 12 4 4 33.333%

문제

서울에서 민승이는 택시운전을 하고 있다. 서울은 1부터 N번까지 숫자로 붙여진 N개의 교차로로 구성되어있다. 그리고 어떤 교차로들은 도로로 연결되어 있는데 이 도로는 너무 좁아서 일방통행만이 가능하다. 민승이는 오랜 택시 경험상 어떤 교차로에서 출발해서 다시 그 교차로로 돌아올 수 없고, 어떠한 교차로 사이에도 두 개 이상의 도로가 없다는 것을 알고 있다.

어느 날 교차로 A에서 민승이는 한 명의 승객을 태웠다. 그리고 그 승객은 그에게 교차로 B로 가자고 했다. 단 그는 몇몇 사람들과 미팅을 갖기 위해 드라이브 도중 교차로 C1, C2, …, Ck를 거쳐야 한다. 단 이 중간 교차로들의 방문 순서는 중요하지 않다. 민승이는 위의 드라이브 조건을 만족하는 경로가 여럿 존재한다는 것을 깨달았지만 얼마나 많은지가 궁금해졌다.

입력

첫 번째 줄에 교차로의 개수인 N(1<=N<=1,000)과 도로의 개수 M이 주어진다. 그 다음 M개에 줄에는 도로의 정보를 알려주는 시작점과 끝점이 주어진다. 다음 줄에는 시작점 A와 끝점 B, 그리고 방문해야할 중간 지점의 개수 K개 주어진다. 마지막 줄에는 공백을 구분으로 C1, C2, …, Ck가 차례대로 주어진다.

출력

첫 번째 줄에 조건을 만족하는 경로의 개수 S를 출력한다. (경로가 존재하지 않을 경우엔 0을 출력한다.) 단 S가 2,000,000,000이 넘는 입력은 주어지지 않는다고 가정하자.

예제 입력

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

예제 출력

1

힌트

출처

  • 문제를 만든 사람: ntopia