E. To Play or Not to Play, That is the Question
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Huize and Jacobo are playing a conquest video game. In the game, there are $$$N$$$ cities and $$$M$$$ bidirectional roads between pairs of cities. Initially, Huize occupies $$$H$$$ cities, and Jacobo occupies $$$J$$$ cities with some soldiers. They have already placed the soldiers, and now it's time to see who wins. The soldiers can be divided into any number of groups and march through all the roads incident to the cities they occupy. Each city is conquered by the first group of soldiers that reaches the city. If multiple groups arrive at the same time, Jacobo's soldiers will conquer the city. Once a city is conquered, the opponent cannot enter it.

The roads can have different lengths, so each road is specifically associated with the travel time between cities. Additionally, some roads are blocked and require a code to open, which can be obtained in exactly one city (not necessarily one of the cities at the ends of the road). The player who conquers that city can use the road from the moment they conquer the city, and the other player cannot use it.

The objective of this game is to occupy more cities than the opponent. Jacobo, who wants to spend more time with his daughter, is only willing to play if he knows he will win. Help Jacobo: if Jacobo is going to win, print two lines, the first with the text "La hora de juego" (without quotes), and the second with the difference between the number of cities Jacobo will occupy and the number of cities Huize will occupy. If Jacobo is going to tie or lose, print in a single line "Hasta luego Huize, es la hora de Olivia" (without quotes).

Input

The input begins with an integer $$$T$$$, the number of test cases.

Each case begins with two integers on a line: $$$N$$$, $$$M$$$.

The following $$$M$$$ lines contain four integers each: $$$u_i$$$, $$$v_i$$$, $$$w_i$$$, $$$c_i$$$, indicating that there is a road connecting cities $$$u_i$$$ and $$$v_i$$$, it takes $$$w_i$$$ minutes to travel, and the secret code is located in city $$$c_i$$$ (if $$$c_i = 0$$$, no code is needed to travel).

The next line contains an integer $$$H$$$.

In the following line, there are $$$H$$$ integers $$$h_i$$$, representing the cities initially occupied by Huize.

The next line contains an integer $$$J$$$.

In the following line, there are $$$J$$$ integers $$$j_i$$$, representing the cities initially occupied by Jacobo.

Output

For each test case, if Jacobo is going to win, write "La hora de juego" and, on a new line, how many more cities than Huize he will occupy. Otherwise, write "Hasta luego Huize, es la hora de Olivia" on a single line.

Scoring
  1. (13 points) $$$M = N-1$$$ and for all $$$1 \leq i \lt N$$$, $$$u_i = i$$$ and $$$v_i = i+1$$$; in other words, the cities form a path. Also, $$$H = J = 1$$$, $$$2 \leq N$$$, and Jacobo and Huize will occupy the two ends of the path.
  2. (9 points) There is no path that requires a code.
  3. (14 points) $$$w_i = 1$$$ for all $$$1 \leq i \leq M$$$.
  4. (24 points) $$$1 \leq N, M \leq 2000$$$, $$$1 \leq T \leq 100$$$, the sum of $$$N$$$ in all cases is less than $$$2000$$$, and the sum of $$$M$$$ in all cases is less than $$$2000$$$.
  5. (21 points) $$$M = N-1$$$ and for all $$$1 \leq i \lt N$$$, $$$u_i = i$$$ and $$$v_i = i+1$$$; in other words, the cities form a path.
  6. (19 points) No additional restrictions.
Example
Input
3
7 8
1 2 2 0
1 4 1 0
2 4 1 1
2 3 1 1
3 7 3 7
3 5 1 6
7 6 3 0
6 5 100 6
2
7 4
1
1
7 8
1 2 2 0
1 4 1 0
2 4 1 1
2 3 1 1
3 7 3 7
3 5 1 3
7 6 3 0
6 5 100 6
2
7 4
1
1
5 4
3 1 116 3
1 4 14 4
4 2 100 2
2 5 2 0
1
3
1
5
Output
Hasta luego Huize, es la hora de Olivia
La hora de juego
1
La hora de juego
3
Note

$$$1 \leq H, J, h_i, j_i, c_i \leq N \leq 2 \times 10^5$$$, $$$H+J \leq N$$$.

$$$0 \leq M \leq \min\left(\frac{N \cdot (N-1)}{2}, 2 \times 10^5\right)$$$.

$$$1 \leq w_i \leq 10^9$$$.

$$$1 \leq T \leq 10000$$$; The sum of $$$N$$$ in all cases is less than $$$2 \times 10^5$$$; The sum of $$$M$$$ in all cases is less than $$$2 \times 10^5$$$.