25560번 - 포탈

놀이동산에 간 현준이와 진우는 $N$개의 방이 있는 미로에 갇히고 말았다! 방들은 $1$부터 $N$까지 번호가 붙어 있고, $N - 1$개의 통로로 서로 연결되어 있으며, 임의의 두 방 사이를 하나 이상의 통로를 통해 이동할 수 있다.

미로에서 탈출하기 위해 현준이와 진우는 게임을 해야 한다. 게임은 두 사람이 번갈아 가면서 차례를 진행하는데, 자신의 차례가 되면 현재 자신이 있는 방과 연결된 통로 중 하나를 선택하고 그 통로를 따라 다른 방으로 이동한다. 첫 번째 차례는 현준이가 진행한다.

만약 현준이와 진우가 같은 방에 위치하게 된다면 즉시 현준이가 승리하고 게임이 끝난다. 두 사람이 각각 $10^{18}$차례를 진행할 동안 현준이가 승리하지 못했다면 진우가 승리하고 게임이 끝난다. 게임이 끝나면 두 사람은 미로를 빠져나갈 수 있는데, 게임에서 진 사람은 벌칙을 수행해야 한다.

그런데 이 미로에는 포탈이 하나 숨겨져 있었다! 포탈은 두 개의 방을 연결하는데, 통로로 직접 연결된 두 방 사이에는 포탈이 존재하지 않는다. 만약 현준이와 진우가 게임을 진행하는 도중 통로를 따라 이동하여 포탈과 연결된 방에 멈추었을 경우, 계속해서 포탈을 따라 이동한 후 차례를 넘겨야 한다. 포탈을 따라 이동하여 포탈과 연결된 방에 멈추었다면 그 차례에는 더이상 움직이지 않는다. 포탈은 양방향이며, 두 사람의 초기 위치는 포탈과 연결된 방이 아니다.

현준이와 진우는 항상 최선의 전략으로 움직인다. 미로의 구조와 포탈, 두 사람의 초기 위치가 주어졌을 때 누가 게임에서 승리할지 구해 보자!

첫째 줄에 방의 수를 나타내는 정수 $N$이 입력된다. $(4 \le N \le 100\,000)$

다음 $N - 1$개의 줄에는 미로의 구조가 주어진다. $i$번째 줄에는 $i$번째 통로가 연결하는 두 방의 번호 $u_i$, $v_i$가 공백으로 구분되어 입력된다.

$N + 1$번째 줄에 처리할 쿼리의 수 $Q$가 입력된다. $(1 \le Q \le 100\,000)$

다음 $Q$개의 줄에는 서로 다른 네 정수 $p_x$, $p_y$, $x$, $y$가 공백으로 구분되어 입력된다. 이것은 포탈이 $p_x$번 방과 $p_y$번 방을 연결하고 현준이의 초기 위치가 $x$번 방, 진우의 초기 위치가 $y$번 방이라는 의미이다. $(1 \le p_x, p_y, x, y \le N)$

미로의 임의의 두 방 사이를 하나 이상의 통로를 통해 이동할 수 있으며, 포탈은 통로로 직접 연결된 두 방 사이에는 존재하지 않는다.

각각의 쿼리에 대해 포탈이 $p_x$번 방과 $p_y$번 방을 연결하고 현준이와 진우의 초기 위치가 각각 $x$번, $y$번 방일 때 게임에서 현준이가 이긴다면 H, 진우가 이긴다면 J를 한 줄에 하나씩 출력한다.