Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

games

trees

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
C3. Game on Tree (Hard)

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis is the hard version of the problem. The only difference in this version is the constraint on $$$t$$$.

Ron and Hermione are playing a game on a tree of $$$n$$$ nodes that are initially inactive. The game consists of $$$t$$$ rounds, each of which starts with a stone on exactly one node, which is considered as activated. A move consists of picking an inactive neighbor of the node with a stone on it and moving the stone there (thus activating this neighbor). Ron makes the first move, after which he alternates with Hermione until no valid move is available. The player that cannot make a move loses the round. If both players play optimally, who wins each round of this game?

Note that all the rounds are played with the same tree; only the starting node changes. Moreover, after each round, all active nodes are considered inactive again.

Input

The first line contains integers $$$n$$$ ($$$2 \leq n \leq 2\times 10^5$$$), $$$t$$$ ($$$1 \leq t \leq n$$$), the number of nodes in the tree and the number of rounds, respectively.

The next $$$n-1$$$ lines contain two integers $$$1 \leq u, v \leq n$$$ each, corresponding to an edge of the tree.

The next line contains $$$t$$$ integers $$$1 \leq u_1 , \dots , u_t \leq n$$$, corresponding to the node where the stone is initially put.

Output

The output consists of $$$t$$$ lines, each line being either "Ron" or "Hermione".

Examples

Input

5 21 21 33 43 51 2

Output

Ron Ron

Input

6 31 22 31 44 54 61 4 6

Output

Hermione Ron Hermione

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/24/2024 03:03:50 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|