33711번 - 내 이름 나무

문제

근성은 나무에 관심이 많다.

종현과 맥X날드에서 햄버거를 먹으며 미래를 논의하던 근성은 험난하디 험난한 코딩 세상에서 산림자원학과의 본질을 지키기 위한 다짐으로 이름을 김트리로 개명하였다. 이를 보고 감명을 받은 많은 전남대 사람들이 '고 속푸리에변환', '정 수자료형인티져', '이 웃오브바운드익셉션' 등의 이름으로 개명하기 시작하였다.

정환은 복학하기 전 전남대의 최신 유행에 따라 개명하려 한다. 하지만 슬프게도 정환이 개명하고자 하는 이름과 같은 이름을 가진 사람이 정환의 주변에 있어 개명을 해도 될지 걱정이 되었다.

고민하던 정환은 임의의 SNS 그룹을 조사하였다. 조사한 그룹에서 어느 한 명이라도 주변 $K$거리 이내의 친구¹와 동일한 이름을 가지는 사람이 있다면, 동일한 이름을 가져도 문제가 없다고 판단하고 개명을 하기로 마음먹었다. 정환이 확인할 SNS에서는 원하는 사람만 이름을 공개하기에 정환은 이름이 공개된 사람들 사이의 중복만 확인한다.

정환이 주어진 상황에서 개명이 가능한지 판단하시오.

¹$K$거리 이내의 친구는 사람을 노드, 친구 사이를 길이 1의 간선으로 보았을 때 두 노드 사이의 최단 거리가 $K$이하인 친구를 말한다.

입력

첫 번째 줄에 정환이 조사하기로 한 SNS 그룹의 사람 수 $N,ドル 사람들 간의 관계 수 $M,ドル 확인할 거리 수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 SNS에 포함된 사람 중 이름이 공개된 사람의 수 $W$가 주어진다.

세 번째 줄부터 $W$개의 줄에 걸쳐 이름이 공개된 사람들의 번호와 이름이 $u$ $s$ 형식으로 주어진다. 이는 $u$번 사람의 이름이 $s$라는 뜻이다. 이때, 서로 다른 이름의 가짓수는 최대 1ドル,000円$개이다.

$ W + 3 $번째 줄부터 $M$개의 줄에 걸쳐 사람들의 관계가 $a$ $b$ 형식으로 주어진다. 이는 $a$번 사람과 $b$번 사람이 서로 친구라는 뜻이다.

출력

첫 번째 줄에 정환이 이름을 변경할 수 있다면 POWERFUL CODING JungHwan을, 변경할 수 없다면 so sad를 출력한다.

제한

• 2ドル \le N \le 35,000円$
• 1ドル \le M \le \min(35,000,円 (N \times (N - 1))/2)$
• 1ドル \le K \le N$
• 1ドル \le W \le N$
• 1ドル \le u \le N$
• 1ドル \le | s | \le 200$
• 1ドル \le a,b \le N,ドル $a \neq b$
• 입력으로 주어지는 모든 수는 정수이다.
• $s$는 알파벳 소문자로 구성되어 있는 문자열이다.

노트