Problem C: Maze

Problem C: Maze

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 488  Solved: 182
[Submit][Status][Web Board]


Yuki is a careless girl and she is designing mazes.

A maze consists of \(n\) rooms and \(m\) passageways. The rooms are numbered from \(1\) to \(n\) and all the passageways are unidirectional, that is the passageway from room \(u\) to \(v\) cannot be passed from room \(v\) to \(u\). Besides, to avoid tourists being trapped in the maze, all the rooms should be connected, that is for every pair of integers \((u,v)\) such that \(1\leq u,v\leq n,u\neq v\), there should be a path from room \(u\) to room \(v\).

Yuki has already designed a "maze". However, due to her carelessness, you need to check whether the maze she designed is a real maze, that is all the rooms in her maze are connected.


The first line contains two integers: \(n\) and \(m\) \((1\leq n,m\leq 200\ 000)\) --- the number of rooms and passageways in the maze.

Each of the next \(m\) lines contains two integers: \(u\) and \(v\) \((1 \leq u,\ v\leq n)\), meaning that there is a unidirectional passageway from room \(u\) to room \(v\).


If all the rooms in the maze are connected, print “Bravo” (without quotation).

Otherwise print “ovarB” (without quotation).

Sample Input

3 3
1 2
2 3
3 2

Sample Output