Under construction

Still being built. Things may change

Hanzo Waiting

Time limit2sMemory limit256 MB

Summary
Each team assigns distinct troll picks to maximize the number of satisfied players; decide whether Wookje's team ends with strictly fewer troll picks.
Level

Medium7 of 10

Topics
Graph, BFS, Binary search, Greedy
Solved
No attempts yet

Problem

Wookje is one win away from promotion to Grandmaster, and he has just seen something terrible: his teammates have started throwing the game.

Just as he is about to give up on the promotion, Wookje notices that the enemy team is throwing too! Now nobody can tell how the match will end.

Each team has NN players, and every player picks one hero before the game starts. Two players on the same team cannot pick the same hero. The game has a huge number of heroes, and MM of them are so bad that picking one decides the outcome of the game. Picking such a hero is called a troll pick. (Both teams play the same game, so the number of troll picks MM is the same for both teams.)

Since both teams are throwing, everyone decides to just have fun. Each player names the troll picks they want out of the MM troll picks, and each team assigns troll picks so that as many of its players as possible get one. A player who gets no troll pick has to settle for a healer.

The game matches players of similar skill, so the team with fewer troll picks wins. Given the troll picks each player on each team wants, determine whether Wookje reaches Grandmaster. A draw gives no points, so it does not count as a promotion. Of course, Wookje is throwing too.

Input

The first line contains the number of players on one team NN (1≤N≤3001 \le N \le 300), the number of troll picks MM (1≤M≤3001 \le M \le 300), and the numbers of wish entries of the two teams K1K_1 and K2K_2 (1≤K1,K2≤5001 \le K_1, K_2 \le 500).

Each of the next K1K_1 lines contains two integers ii and jj (1≤i≤N1 \le i \le N, 1≤j≤M1 \le j \le M), meaning that player ii on Wookje's team wants troll pick jj.

The next K2K_2 lines give the troll picks wanted by the players on the enemy team in the same format.

Output

Print 네 다음 힐딱이 if Wookje gets promoted, and 그만 알아보자 otherwise. Print these Korean phrases exactly as shown.

Examples2

  1. Example 1

    Input
    5 4 5 3
    1 1
    2 2
    3 3
    4 4
    5 2
    1 1
    2 1
    3 1
    
    Expected output
    그만 알아보자
    
  2. Example 2

    Input
    4 4 5 8
    1 1
    1 2
    2 1
    3 3
    4 3
    1 1
    1 4
    2 1
    2 2
    2 3
    3 2
    3 3
    4 3
    
    Expected output
    네 다음 힐딱이