25488번 - 토큰

동훈이는 친구 찬경이에게 $N$개의 정점과 $M$개의 단방향 간선이 있는 그래프를 선물로 줬다.

선물을 받은 기쁨도 잠시, 찬경이는 그래프에 딸려 온 카드 두 장을 보고 동훈이가 자신을 골탕 먹이려고 미션을 준비했다는 것을 깨닫게 되었다.

찬경이가 해야 하는 미션은 다음과 같다.

• 카드 두 장 중 한 장은 빨간색이고, 다른 한 장은 파란색이다. 각각의 카드에는 $1$부터 $N$까지의 정점 번호 중 $P$개가 적혀 있다. 각각의 카드에 적힌 정점 번호는 모두 다르며, 한 정점 번호가 두 카드에 모두 적혀 있을 수 있다. 이때 빨간 카드에 적힌 번호의 정점들에 토큰을 하나씩 올려놓은 상태를 '첫 번째 상태', 파란 카드에 적힌 번호의 정점들에 토큰을 하나씩 올려놓은 상태를 '두 번째 상태'라고 하자.
• 그래프에 토큰을 올려놓아 첫 번째 상태가 되도록 만든다.
• 토큰을 움직이는 과정을 반복해서 두 번째 상태를 만든다. 정점 $u$에서 정점 $v$로 가는 간선이 존재하고, 정점 $u$에 토큰이 있고 정점 $v$에는 토큰이 없을 경우 정점 $u$에 있는 토큰을 정점 $v$로 움직일 수 있다.
• 토큰을 움직이는 과정을 반복해서 첫 번째 상태를 만든다.

찬경이는 동훈이의 성격을 알기 때문에, 미션이 처음부터 불가능할지도 모른다는 의심을 하고 있다. 만약 미션을 수행하는 것이 불가능하다면 찬경이는 귀찮게 고생하지 않고 다른 일을 하러 갈 것이다. 찬경이를 도와주자!

첫째 줄에 정점의 개수 $N$과 단방향 간선의 개수 $M$이 주어진다. $(1 \le N \le 200\,000, 0 \le M \le \min(N \cdot (N - 1), 200\,000))$

다음 $M$개의 줄에는 간선의 정보가 주어진다. $i$번째 줄에는 두 정수 $u_i, v_i$가 주어지며, 이는 $u_i$번 정점에서 $v_i$번 정점으로 가는 단방향 간선이 존재한다는 의미이다. 중복 간선이나 자기 자신으로 가는 간선은 입력되지 않는다.

$(M + 2)$번째 줄에 각 카드에 적힌 정점의 수 $P$가 주어진다. $(0 \le P \le N)$

$(M + 3)$번째 줄에 $P$개의 서로 다른 양의 정수 $a_1, a_2, \ldots, a_P$가 주어진다. 이것은 빨간 카드에 적힌 토큰을 놓을 정점의 번호이다. $(1 \le a_i \le N)$

$(M + 4)$번째 줄에 $P$개의 서로 다른 양의 정수 $b_1, b_2, \ldots, b_P$가 주어진다. 이것은 파란 카드에 적힌 토큰을 놓을 정점의 번호이다. $(1 \le b_i \le N)$

각 줄에 입력되는 값들은 전부 공백으로 구분되어 주어진다.

찬경이가 미션을 수행할 수 있다면 YES, 수행할 수 없다면 NO를 출력한다.