The Two Cows Game on a Directed Graph

Farmer John’s cows love to play a two‐player game on a directed graph. You are given a directed graph with (N) vertices and (M) edges ((2 \le N \le 10^5), (1 \le M \le 2\cdot10^5)). Two distinct markers are placed on two different vertices. The game is played in rounds as follows:

1. In each round, the first player (Brain) chooses one of the two markers to move.
2. Then, the second player (Hooves) selects an outgoing edge from the chosen marker’s current vertex and moves the marker along that edge.

During the game, the two markers are never allowed to occupy the same vertex. If at any moment Hooves is unable to choose a legal move (i.e. the chosen marker has no outgoing edge leading to a vertex that is not occupied by the other marker), then Brain wins immediately. Otherwise, if the game can continue indefinitely, then Hooves wins.

You are given (Q) queries. Each query specifies the initial positions of the two markers. For each query, determine which player wins if both players play optimally.

The key observation is that Brain wins from a state ((u,v)) if and only if there exists an option (choosing either marker) such that either there is no legal move available, or for every legal move the game transitions to a state that is winning for Brain. Otherwise, Hooves can force the game to continue forever, and thus wins.

All formulas are rendered in (\LaTeX) format.

inputFormat

The input begins with two integers (N) and (M) denoting the number of vertices and edges. The next (M) lines each contain two integers (u) and (v) indicating a directed edge from vertex (u) to vertex (v).

Then an integer (Q) follows, representing the number of queries. Each of the next (Q) lines contains two integers, representing the starting vertices of the two markers. It is guaranteed that in the initial configuration the two markers are on distinct vertices.

outputFormat

For each query, print a single line with either “Brain” if Brain wins, or “Hooves” if Hooves wins.

sample

3 3
1 2
2 3
3 1
2
1 2
2 3

Brain
Brain