27503번 - 요가 수업

2040년, 성현이는 20년간 요가를 수련한 끝에 신촌 제일의 요가 마스터가 되었다. 신촌연합 알고리즘 캠프에서는 그런 성현이에게 캠프 수강생들을 위한 요가 수업을 의뢰했다. 그래서 성현이는 자신이 아는 $N$개의 요가 동작들 중 $M$개의 서로 다른 동작을 선별하여 요가 수업을 구성하였다.

그런데 성현이가 신촌에 널리 알려진 요가 지도서 '요가의 흐름'을 검토한 결과, 요가 수업을 구성할 때 고려해야 할 두 가지가 있었다. 성현이는 자신의 수업이 여기에 어긋날 수 있다는 것을 깨닫고 이것에 맞게 수업 내용을 고쳐 보려고 한다.

첫번째는 수업에 포함된 동작들 중 $C$개의 동작들에 대해서는 그 동작을 대체할 수 있는 동작이 있다는 것이다. 어떠한 이유로든 수업에 포함될 수 없는 동작이 있을 수 있는데, 이 경우 그 동작을 '요가의 흐름'에서 제시하는 다른 동작으로 대체할 수 있다. '요가의 흐름'에서는 이런 동작의 쌍을 $C$개 제시하며 그 쌍을 이루는 동작에 대해서는 둘 중 적어도 하나만 수업에 포함되면 된다고 설명하고 있다. 이 내용에 의해 고쳐진 수업은 $M$개보다 적은 동작으로 구성되어 있을 수도 있다.

두번째는 '요가의 흐름'에서 제시하는 요가 동작의 쌍 $K$개에 대해서는 그 쌍을 이루는 동작이 수업에 동시에 포함되어서는 안 된다는 것이다. 이는 수업에서 같이 진행할 시 수업의 흐름을 해칠 수 있는 동작들이 있기 때문이다. 이런 동작의 쌍들은 쌍을 이루는 두 동작 중 하나만 수업에 포함되거나 둘 모두 수업에 포함되지 않아야 한다.

하지만 성현이는 수업 구상에만 너무 많은 시간을 쓰는 바람에 시간이 부족해서 자신이 구상한 수업을 고치지는 못했다. 따라서 우리는 성현이가 '요가의 흐름'의 내용에 맞게 수업을 고칠 수 있는지 알아봐 줘야 한다. 그것을 검사하는 프로그램을 작성해 보자.

성현이는 요가 동작을 이름 대신 숫자로 기억하기 때문에 주어지는 요가 동작들은 $1$부터 $N$사이의 정수로 표현된다.

성현이가 구상한 요가 수업의 내용이 다음과 같이 주어진다.

첫째 줄에는 성현이가 아는 요가 동작의 개수 $N$과 그 중 성현이가 구성한 수업을 이루는 동작의 개수 $M$, 대체할 수 있는 동작이 있는 동작의 개수 $C$, 동시에 수업에 포함하면 안 되는 요가 동작 쌍의 개수 $K$가 주어진다. ($1 \le M \le N \le 500,000, 0 \le C \le M, 0 \le K \le 300,000$)

다음 줄에는 현재 성현이의 수업을 구성하고 있는 요가 동작들의 번호를 나타내는 $M$개의 서로 다른 정수 $A_1, A_2, ..., A_M$이 주어진다. ($1 \le A_i \le N$)

그 다음 $C$개의 줄에는 원래 동작 $u$과 $u$를 대체할 수 있는 동작 $v$로 이루어진 쌍 $C$개가 $u, v$의 형태로 주어진다. 동작 $u$와 동작 $v$ 중 하나 이상을 수업에 포함하면 된다는 뜻이다. ($1 \le u \le N, 1 \le v \le N, u \ne v$, $u$는 $A_1, A_2, ..., A_M$ 중 하나이고 주어지는 $u$는 모두 서로 다르다)

그 다음 $K$개의 줄에는 한 수업에 함께 포함되면 안 되는 두 가지 동작 $a, b$의 번호가 각각 주어진다. 이는 $a$번 동작과 $b$번 동작이 수업에 함께 포함되면 안 된다는 뜻이다. ($1 \le a, b \le N, a \ne b$)

성현이가 구성한 수업을 '요가의 흐름'에서 제시하는 두 가지 내용에 맞게 고칠 수 있으면 YES, 만족하지 못하면 NO를 출력한다.