20295번 - 사탕 배달

문제

윤제가 사는 마을에는 $N$개의 사탕 가게가 있다. 사탕 가게는 1ドル$번부터 $N$번까지 번호가 매겨져 있다. 각 가게에서는 다섯 가지 종류의 사탕 중 하나만을 판매한다. 또한 사탕 가게들을 잇는 도로 $N-1$개로 이루어진 도로망이 있다. 모든 도로는 지나는 데에 1ドル$의 시간이 필요하며, 도로망을 이용해 한 사탕 가게에서 다른 모든 사탕 가게로 이동할 수 있다.

윤제는 오늘 $M$명의 친구를 한 명씩 순서대로 만나기로 했는데, 각 친구를 만나러 가는 길에 만날 친구가 좋아하는 종류의 사탕을 사다 주어야 한다. 이에 실패하면 친구들은 화가 나 떠나버린다.

윤제는 친구들을 빠르게 만나기 위해 한 친구를 만나고 나서 곧장 다음 친구를 만나러 출발한다. 시간을 최대한 단축하기 위해 언제나 최단 경로로 이동하며, 그 경로를 지나는 도중에 만나는 사탕 가게에 들러서 사탕을 산다. 친구가 있는 곳에 있는 가게에서 사탕을 사는 것도 가능하다. 다만, 윤제는 주머니가 작아서 사탕을 한 개만 들고 다닐 수 있다. 즉 어떤 친구 A를 만나러 가는 길에 또 다른 친구 B를 위한 사탕을 미리 사는 것은 불가능하다.

윤제는 자신을 떠날 친구들을 미리 파악하기 위해 각 친구에게 사탕을 사다 줄 수 있는지를 알고 싶어 한다. 윤제는 시작 위치를 자유롭게 선택할 수 있다. 윤제를 도와 각 친구가 좋아하는 사탕을 사다 줄 수 있는지 알려주는 프로그램을 작성하자.

입력

첫째 줄에 사탕 가게의 개수를 나타내는 정수 $N$이 주어진다. (1ドル \leq N \leq 100\ 000$)

둘째 줄에 각 사탕 가게에서 판매하는 사탕의 종류를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. 사탕의 종류는 1ドル$과 5ドル$ 사이의 양의 정수로 표현된다.

셋째 줄부터 $N-1$개의 줄에 걸쳐 도로의 정보를 나타내는 $u, v$ 가 주어진다. 이는 $u$번 사탕 가게와 $v$번 사탕 가게를 잇는 양방향 도로가 존재한다는 의미이다. (1ドル \leq u, v \leq N,ドル $u \neq v$)

다음 줄에 친구의 수를 나타내는 정수 $M$이 주어진다. (1ドル \leq M \leq 100\ 000$)

다음 $M$개 줄에 걸쳐 각 친구가 서 있는 가게의 번호와 좋아하는 사탕의 종류가 약속 시간이 빠른 순으로 주어진다. 여러 명의 친구가 같은 가게 앞에 서 있을 수도 있다.

출력

약속 시간이 빠른 순서대로, 각 친구가 좋아하는 종류의 사탕을 사다 줄 수 있다면 PLAY를, 아니라면 CRY를 한 줄에 하나씩 출력한다.

제한

노트