25335번 - Gravity Hackenbush

성현이는 아래와 같은 방식으로 진행되는 2인용 게임인 Gravity Hackenbush를 만들어서 나정휘에게 선물로 줬다.

Gravity Hackenbush의 준비 과정은 다음과 같다.

1. 땅을 의미하는 직선 $y = 0$을 그린다.
2. $N$개의 점을 찍는다. 땅보다 더 낮은 곳에는 점을 찍을 수 없다.
3. 2번 과정에서 찍은 $N$개의 점 중 서로 다른 두 점을 연결하는 $M$개의 선을 그린다. 땅과 평행한 선은 그릴 수 없다.
4. 각 선을 빨간색, 파란색, 또는 초록색 중 하나로 칠한다.

Gravity Hackenbush의 게임은 다음과 같이 진행된다.

1. 두 플레이어는 승부가 정해질 때까지 번갈아가면서 턴을 갖는다. 1번 플레이어가 먼저 시작한다.
2. 각 플레이어는 특정 색깔의 선만 자를 수 있다.
   • 빨간색 선은 1번 플레이어만 자를 수 있다.
   • 파란색 선은 2번 플레이어만 자를 수 있다.
   • 초록색 선은 두 플레이어 모두가 자를 수 있다.
3. 각 플레이어는 자신의 턴에 자를 수 있는 선 중 원하는 것을 하나 골라서 자른다.
4. 자신의 턴이 되었을 때 자를 수 있는 선이 없는 플레이어는 패배한다.
5. 선을 자른 다음, 땅과 직간접적으로 연결되지 않은 점과 선들은 연결된 점 또는 선이 땅에 닿을 때까지 내려간다.
6. 떨어지는 과정에서 연결되어 있지 않은 점 또는 선들이 만나더라도 연결되지 않은 것으로 취급한다.

아래 그림은 Gravity Hackenbush에서 선을 하나 자른 뒤의 상태를 보여준다.

게임을 선물받은 나정휘는 난정휘와 함께 게임을 여러 번 플레이하면서 필승법을 찾아냈다. 마침 천하제일 코딩대회에 낼 문제가 부족했던 나정휘는 필승법을 찾는 문제를 대회에 출제하기로 했다.

게임의 초기 상태가 주어지면 나정휘와 난정휘가 모두 최선을 다해 플레이했을 때 누가 이기는지 구해보자. 나정휘가 1번 플레이어, 난정휘가 2번 플레이어다.

첫째 줄에 점과 선의 개수를 나타내는 정수 $N, M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 200\,000$, $0 \leq M \leq 500\,000$)

둘째 줄부터 $N$개의 줄에 $i$번 점의 좌표 $x_i, y_i$가 한 줄에 하나씩 공백으로 구분되어 주어진다. ($-10^9 \leq x_i \leq 10^9$, $0 \leq y_i \leq 10^9$)

다음 $M$개의 줄에 $i$번째 선이 연결하는 두 점의 번호 $v_i, w_i$와 색깔 $c_i$가 공백으로 구분되어 주어진다. ($1 \leq v_i,w_i \leq N$, $v_i \neq w_i$, $c_i$는 R 또는 G 또는 B)

두 점의 좌표는 모두 서로 다르고, 연결하는 두 점의 쌍이 동일한 선이 여러 개 주어지지 않는다. 또한, x축과 평행한 선은 주어지지 않는다.

처음에 모든 점들은 땅과 직간접적으로 연결되어 있다.

입력으로 주어지는 수는 모두 정수이다.

두 사람이 최선을 다해서 플레이할 때, 나정휘가 이긴다면 "jhnah917", 난정휘가 이긴다면 "jhnan917"을 출력한다.