게임이론

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

효원이는 정점 $s$에서 시작한다. 두 사람은 번갈아 가며 그래프 위를 움직이면서 돌을 제거한다.

• 현재 위치한 정점을 $u$, 정점 $u$에 있는 돌의 개수를 $w$라고 하자. 정점 $u$에서 돌을 최소 $1$개, 최대 $w$개까지 제거한다.
• $u$에 연결된 정점으로 이동한다. Loop가 있으므로 $u$에서 $u$로 이동하는 것도 가능하다. 도착한 정점의 돌이 $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"를 따옴표 없이 출력한다.