작업

면접 대비

시간 제한1초메모리 제한512 MB

요약

작업 의존 관계를 나타내는 DAG가 주어질 때, 작업 X를 끝내기 전에 먼저 해야 하는 작업의 수를 구한다.

문제

민상이는 자신이 해야 할 작업 $N$ 개를 아래와 같이 작업 순서도로 그려보았다.

위 그림에서 5번 작업을 하기 위해서는 제일 먼저 2번 작업을 끝내야 하고, 그다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야 하는 작업이 없으므로 바로 시작할 수 있다.

작업 순서를 정할 때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야 하고, B 작업을 하려면 A 작업을 먼저 해야 하는 상황은 없다.

민상이에게는 오늘 반드시 끝내야 하는 작업 $X$ 가 있다. 민상이가 작업 $X$ 를 끝내기 위해 먼저 해야 하는 작업의 개수를 구하자.

첫째 줄에 민상이가 작업할 개수 $N$ 과 작업 순서 정보의 개수 $M$ 이 공백으로 구분되어 주어진다.

둘째 줄부터 $M + 1$ 번째 줄까지 작업 $A_i$ 와 작업 $B_i$ 가 공백으로 구분되어 주어진다. 두 값의 의미는 작업 $B_i$ 를 하기 위해 바로 이전에 작업 $A_i$ 를 먼저 해야 한다는 것이다. 중복된 정보는 주어지지 않는다.

마지막 줄에는 민상이가 오늘 반드시 끝내야 하는 작업 $X$ 가 주어진다.

민상이가 작업 $X$ 를 하기 위해 먼저 해야 하는 일의 개수를 출력한다.