20504번 - I번은 쉬운 문제

2030년, Farmer John은 선린 인터넷 컴퍼니에서 소프트웨어 개발자이자 검색 팀장으로 근무하고 있다. John의 강한 의지에 따라 검색 팀에서는 모든 소프트웨어의 개발을 테스트 주도 개발(test-driven development) 형태로 수행하고 있다.

검색팀에서는 효율적인 검색을 위해 새로운 프로그램을 만들고 있고, 이 프로그램은 여러 함수로 구성되어 있다. 하나의 함수는 실행되는 동안 0개 이상의 다른 함수를 호출하게 된다.

예를 들어, 프로그램이 다음과 같이 3개의 함수 f, g, h로 이루어져 있다면, f를 호출했을 때는 호출될 가능성이 있는 추가적인 함수가 없고, g를 호출했을 때는 f가 호출될 가능성이 존재하며, h를 실행했을 때는 f, g, h가 호출될 가능성이 존재한다.

function<void> f(x: int) {
    // do something (다른 함수를 호출하지는 않는다.)
}

function<void> g(x: int) {
    // do something (다른 함수를 호출하지는 않는다.)
    if (condition1) f(x);
}

function<int> h(x: int) {
    if (condition2) f(x);
    else g(x);
    if (condition3) h(x-1);
    return x;
}

이 프로그램의 테스트를 위해 여러 테스트 케이스가 만들어져 있고, 하나의 테스트 케이스는 어떤 함수 하나를 호출하는 방식으로 구성되어 있다. 하지만, 모든 테스트 케이스를 실행하기에는 테스트 케이스의 수가 많아 비효율적이다. 따라서, John은 테스트 케이스 중 일부만을 선택해 실행해보되, 선택한 테스트 케이스를 실행하는 과정에서 모든 함수가 호출될 가능성이 존재하도록 하고자 한다.

각 함수마다 실행 과정에서 호출할 가능성이 있는 함수들의 목록이 주어질 때, John이 선택해야 하는 테스트 케이스의 최소 개수를 구하여라.

첫 번째 줄에 함수의 수 $N$과 함수의 호출 관계의 수 $M$이 사이에 공백을 두고 주어진다.

이후 $M$개의 줄에 걸쳐 두 정수 $u, v$가 사이에 공백을 두고 주어진다. 이는 함수 $u$를 호출했을 때, 함수 $u$가 실행되는 동안 함수 $v$를 직접 호출할 가능성이 존재함을 의미한다. 반대로, 입력으로 주어지지 않은 $u, v$ 쌍의 경우, 함수 $u$가 실행되는 동안 함수 $v$를 직접 호출할 가능성이 존재하지 않는다고 가정하라.

이후 정수 $T$가 주어진다. $T$는 John이 만든 테스트 케이스의 수를 의미한다.

이후 $T$개의 줄에 걸쳐 한 줄에 하나씩 $t_i (1 \le i \le T)$가 주어진다. 이는, $i$번째 테스트 케이스가 함수 $t_i$를 호출하는 방식으로 구성되어 있음을 의미한다.

John이 선택해야 하는 테스트 케이스의 최소 개수를 출력한다.

단, 모든 테스트 케이스를 전부 호출해도 테스트 과정에서 호출될 가능성이 없는 함수가 존재한다면, -1을 출력한다.

• $1 \le N \le 200\,000$
• $1 \le M \le 300\,000$
• $1 \le T \le N$
• $1 \le u, v \le N$
• $1 \le t_i \le N$
• 모든 $(u, v)$ 쌍들은 서로 다르다.
• 모든 $t_i$들은 서로 다르다.