Fallleaves is struggling with a game called “Pull the Box”, and he wants to know if it is possible to win the game.
The game is played on an undirected graph with $\textstyle n$ nodes and $\textstyle m$ edges, without multiple edges or self-loops. Nodes are numbered from $\textstyle 1$ to $\textstyle n$. The player starts at node $\textstyle x$ and can move along the edges but cannot overlap with the box. The goal is to “pull” a box, initially located at node $\textstyle 1$, to node $\textstyle n$. For two **different** edges $\textstyle (u,v)$ and $\textstyle (v,w)$, where $\textstyle u$, $\textstyle v$, and $\textstyle w$ are **distinct**, if the box is at node $\textstyle u$ and the player is at node $\textstyle v$, the player can move the box to node $\textstyle v$ and move himself to node $\textstyle w$. Note that $\textstyle u$ and $\textstyle w$ cannot be the same, i.e., the player cannot move through the box.
Fallleaves wants you to write a program to determine whether the player can achieve the game’s goal and, if possible, the minimum number of edges the player should move through before achieving the game’s goal.
输入格式
Fallleaves is struggling with a game called “Pull the Box”, and he wants to know if it is possible to win the game.
The game is played on an undirected graph with $\textstyle n$ nodes and $\textstyle m$ edges, without multiple edges or self-loops. Nodes are numbered from $\textstyle 1$ to $\textstyle n$. The player starts at node $\textstyle x$ and can move along the edges but cannot overlap with the box. The goal is to “pull” a box, initially located at node $\textstyle 1$, to node $\textstyle n$. For two **different** edges $\textstyle (u,v)$ and $\textstyle (v,w)$, where $\textstyle u$, $\textstyle v$, and $\textstyle w$ are **distinct**, if the box is at node $\textstyle u$ and the player is at node $\textstyle v$, the player can move the box to node $\textstyle v$ and move himself to node $\textstyle w$. Note that $\textstyle u$ and $\textstyle w$ cannot be the same, i.e., the player cannot move through the box.
Fallleaves wants you to write a program to determine whether the player can achieve the game’s goal and, if possible, the minimum number of edges the player should move through before achieving the game’s goal.
输出格式
For each test case, if the player can achieve the game’s goal, output “Vegetable fallleaves” on the first line, and on the second line, output the minimum number of moves required to achieve the goal. Otherwise, output “Boring Game” in a single line.
Vegetable fallleaves
2
Vegetable fallleaves
8
Boring Game
数据范围与提示
In sample case 2:
Initially, the player is at point $\textstyle 4$, and the box is at point $\textstyle 1$.
The player moves along $\textstyle 4 \to 5 \to 6$. ($\textstyle 2$ moves in this step. $\textstyle 2$ moves in total.)
The player pulls the box to point $\textstyle 6$. The player goes to point $\textstyle 5$. ($\textstyle 1$ move in this step. $\textstyle 3$ moves in total.)
The player moves along $\textstyle 5 \to 3 \to 2 \to 1$. ($\textstyle 3$ moves in this step. $\textstyle 6$ moves in total.)
The player pulls the box to point $\textstyle 1$. The player goes to point $\textstyle 8$. ($\textstyle 1$ move in this step. $\textstyle 7$ moves in total.)
The player pulls the box to point $\textstyle 8$. The player goes to point $\textstyle 7$. ($\textstyle 1$ move in this step. $\textstyle 8$ moves in total.)
The player moved through $\textstyle 8$ edges in total and achieved the goal. So you output “Vegetable fallleaves” in the first line. As $\textstyle 8$ can be shown to be the minimum moves required to achieve the goal, you output “8” in the second line.