34698번 - Between

문제

1ドル$부터 $N$까지 번호가 붙은 $N$개의 정점과, $M$개의 간선으로 구성된 방향 무가중치 그래프가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• $a$ $b$ $k$ $p_1 \cdots p_k$: $a$번 정점에서 $b$번 정점으로 가는 최단경로가 존재하며, 이들 중 $p_1, \cdots, p_k$번 정점을 모두 지나는 최단경로가 존재한다면 YES, 아니라면 NO를 출력한다. 이때, $p_1, \cdots, p_k$를 순서대로 지날 필요는 없다.

입력

첫째 줄에 그래프의 정점의 개수 $N,ドル 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(2\le N\le 2,000円$; 1ドル\le M\le 20,000円)$

다음 $M$개의 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. 이는 $a$번 정점에서 $b$번 정점으로 향하는 단방향 간선이 존재함을 의미한다. $(1\le a,b\le N$; $a\neq b)$

다음 줄에는 쿼리의 개수 $Q$가 주어진다. $(1\le Q\le 10,000円)$

다음 $Q$개의 줄에 걸쳐 각 줄에는

• 정점의 번호 $a,ドル $b$ $(1\le a,b\le N)$
• 지나야 하는 정점의 개수 $k$ $(0\le k\le N - 2)$
• $k > 0$인 경우, 지나야 하는 $k$개의 정점의 번호 $p_1, \cdots, p_k$ $(1\le p_i\le N$; $a,ドル $b,ドル $p_1,ドル $\cdots,ドル $p_k$는 모두 다르다.$)$

가 공백으로 구분되어 주어진다.

모든 쿼리의 $k$의 합은 100ドル,000円$을 넘지 않는다.

출력

한 줄에 하나씩, 각각의 쿼리의 결과를 순서대로 출력한다.

제한

노트