스타워즈

미래에 인류는 우주를 식민지화했고, 외계 종족과 전쟁 중이다. 우주에는 많은 항성계가 있으며, 이 항성계는 두 종류로 나눌 수 있다. 인류가 지배하는 항성계와 그렇지 않은 항성계다. 인류는 여러 항성계에 군사 기지를 세웠는데, 이 중 일부는 인류가 지배하는 항성계이고 나머지는 그렇지 않다. 항성계 사이의 거리는 매우 멀어서 두 항성계를 이동하는 유일한 방법은 웜홀을 이용하는 것이다. 그러나 모든 항성계 쌍이 웜홀로 연결되어 있지는 않으며, 웜홀은 한 방향으로만 이동한다. 인류의 우주선이 인류가 지배하는 항성계에서 출발해 어떤 항성계의 군사 기지로 이동하려 할 때, 우주선은 자신이 외계 스파이선이 아니라 인류의 우주선임을 증명하는 일련의 인증서를 받아야 한다. 우주선은 웜홀을 통해 두 항성계 사이를 이동하며 웜홀에서 해당 인증서를 받는다. 두 항성계 사이에는 서로 다른 인증서를 가진 여러 웜홀이 있을 수 있다. 또한 한 항성계에서 서로 다른 모든 항성계로 같은 인증서를 가진 여러 웜홀이 나올 수도 있다. 항성계는 시간 여행을 위한 자기 자신으로 향하는 웜홀도 가질 수 있다. 우주선이 군사 기지에 도착하면, 수집한 인증서를 수집한 순서대로 검사하여 그 우주선이 인류가 지배하는 항성계에서 출발했는지 확인한다. 그러나 인류는 게을러서 인증서의 나열이 인류가 지배하는 임의의 항성계에서 임의의 군사 기지로 가는 경로와 일치하는지만 확인한다.

외계인은 인류가 게으르기 때문에 인류가 지배하지 않는 항성계에서 군사 기지로 가는 같은 인증서 나열을 가진 경로가 있는지 확인하지 않는다는 사실을 즉시 알아낸다. 외계 스파이는 인류의 군사 기지에 잠입하려 한다. 따라서 인류가 지배하는 항성계에서 군사 기지로 이동하는 우주선이 수집할 인증서 나열과 같은 인증서 나열을 만들어 내는 군사 기지로 가는 경로를 찾으려 한다. 그러나 외계인은 인류가 지배하는 항성계에서 출발할 수 없지만, 출발한 뒤에는 인류가 지배하는 항성계를 방문할 수 있다.

외계 스파이인 당신의 임무는 인류가 지배하지 않는 항성계에서 군사 기지 Bi로 가는 경로 중, 인류로 통과할 수 있게 해 주는 인증서 나열을 만들어 내는 경로가 있는지 판단하는 것이다. 즉, 이 인증서 나열은 인류가 지배하는 항성계에서 군사 기지 Bj로 이동할 때 수집할 수 있는 인증서 나열과 같다. Bi와 Bj는 달라도 된다.

우주는 N개의 항성계로 이루어져 있다. 그중 일부는 인류가 지배하는 항성계로 특별히 표시되어 있고, 일부는 군사 기지가 있는 항성계로 특별히 표시되어 있다. 항성계는 인류가 지배하면서 군사 기지가 있을 수도 있고, 둘 중 하나만 해당할 수도 있으며, 둘 다 아닐 수도 있다. 일부 항성계는 단방향 웜홀로 연결되어 있다. 우주선이 웜홀을 통과하면 특별한 인증서를 받는다. 인증서에는 여러 종류가 있다.

프로그램은 표준 입력에서 데이터를 읽는다. 입력의 첫째 줄에는 공백으로 구분된 다섯 정수 N, W, C, H, M이 주어진다. N (1 ≤ N ≤ 1,000)은 항성계의 수다. 항성계에는 0부터 N−1까지 서로 다른 정수가 붙어 있다. W (1 ≤ W ≤ 8000)는 웜홀의 수다. C (1 ≤ C ≤ 20)는 서로 다른 인증서의 수다. 다음 줄에는 공백으로 구분된 H (1 ≤ H ≤ N)개의 정수가 주어지며, 이는 인류가 지배하는 항성계에 해당한다. 다음 줄에는 공백으로 구분된 M (1 ≤ M ≤ N)개의 정수가 주어지며, 이는 군사 기지가 있는 항성계를 표시한다. 남은 W개 줄에는 웜홀을 나타내는 세 정수 s, c, t가 공백으로 구분되어 한 줄에 하나씩 주어진다. 각 웜홀에서 s는 웜홀의 출발 항성계, c는 웜홀이 주는 인증서, t는 웜홀의 도착 항성계이며, 0 ≤ s, t ≤ N − 1, 1 ≤ c ≤ C다. 웜홀은 s = t일 수 있다.

프로그램은 표준 출력에 결과를 쓴다. 외계인이 군사 기지에 잠입할 방법이 있으면 YES, 없으면 NO를 출력한다.