16142번 - 게임이론 서브태스크

효원이랑 승재는 다음과 같은 게임을 한다. 게임은 정점 $1,2,\cdots,n$ 사이를 간선으로 연결해서 만든 그래프 위에서 진행되며, 이 그래프는 임의의 두 정점 사이에 경로가 존재하고, 모든 정점은 자기 자신과 연결해주는 loop를 가졌다. 각 정점 $i$마다 돌을 $w_i>0$개 놓은 상태로 시작한다.

효원이는 정점 $s$부터 시작한다. 효원이랑 승재는 순서를 바꿔가며 다음과 같이 그래프 위에서 움직이며 돌을 제거한다.

• 현재 위치한 정점을 $u$, 정점 $u$에 있는 돌의 개수가 $w$라고 하자. 최소 $1$개, 최대 $w$개까지 정점 $u$에 있는 돌을 제거한다.
• $u$에 연결된 정점으로 이동한다. Loop가 있으므로 $u$에서 $u$로 이동하는 것도 가능하다. 도착한 정점에 돌의 개수가 $0$개라면 한 번 더 이동해야 한다. 돌의 개수가 $0$이 아닌 정점에 도착할 때까지 돌의 개수가 $0$인 정점은 통과한다. $0$이 아닌 정점에 정지하면, 상대방의 턴이 시작한다.

마지막 돌을 제거하는 사람이 이긴다. 다음은 한 게임 플레이의 예시다. 아직 효원이랑 승재가 규칙을 잘 모르는 상태로 플레이를 해서 최적으로 플레이하지 않았을 수도 있다.

이제 효원이랑 승재는 이 게임의 규칙을 잘 이해한다. 두 명 모두 최적으로 게임을 할 경우, 누가 이기는지 판정하는 프로그램을 작성하시오.

첫째 줄에는 정점의 수 $n$, 간선의 수 $m$, 게임을 시작하는 정점 $s$가 주어진다. 그래프는 임의의 두 정점 사이에 경로가 존재하고, 모든 정점은 자기 자신과 연결하는 loop를 가진다. 그래프의 크기는 $1\leq n\leq 50,000$, $2n-1\leq m\leq 500,000$을 만족한다.

둘째 줄에는 각 정점에 있는 돌의 개수 $w_1,w_2,\cdots,w_n$가 공백으로 구분되어 주어진다. 모든 정점에서 돌의 수는 $1$개 이상 $2^{20}$개 미만이다.

셋째 줄부터 $(m+2)$번째 줄까지 간선에 관한 정보가 두 수 $u$와 $v$로 주어진다. 이는 $u$와 $v$ 사이에 무방향 간선이 있다는 의미이다. $u=v$일 수 있다.

효원이랑 승재 둘다 최적으로 게임을 할 경우, 이기는 사람을 출력하라. 효원이가 이기는 경우 "hwy", 승재가 이기는 경우 "sjh"을 따옴표 없이 출력하라.

추가 제한 조건이 없다.