题目描述

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 $n$ nodes and $m$ edges, without multiple edges or self-loops. Nodes are numbered from $1$ to $n$. The player starts at node $x$ and can move along the edges but cannot overlap with the box. The goal is to “pull” a box, initially located at node $1$, to node $n$. For two different edges $(u,v)$ and $(v,w)$, where $u$, $v$, and $w$ are distinct, if the box is at node $u$ and the player is at node $v$, the player can move the box to node $v$ and move himself to node $w$. Note that $u$ and $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.官方中文

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^5$). The description of the test cases follows. The first line of each test case contains three integers $n, m, x$ ($\textstyle 3 \leq n \leq 10^6, 0 \leq m \leq 10^6, 2 \leq x \leq n$), representing the number of nodes, the number of edges, and the starting node of the player, respectively. The next $m$ lines each contain two integers $u, v$ ($1 \leq u, v \leq n, u \neq v$), representing an undirected edge connecting nodes $u$ and $v$. It is guaranteed that there is no multiple edges or self-loops. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$, and the sum of $m$ over all test cases does not exceed $10^6$.官方中文

输出格式

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.

说明

In sample case 2: 官方中文

Initially, the player is at point $4$, and the box is at point $1$. The player moves along $4 \to 5 \to 6$. ($2$ moves in this step. $2$ moves in total.) The player pulls the box to point $6$. The player goes to point $5$. ($1$ move in this step. $3$ moves in total.) The player moves along $5 \to 3 \to 2 \to 1$. ($3$ moves in this step. $6$ moves in total.) The player pulls the box to point $1$. The player goes to point $8$. ($1$ move in this step. $7$ moves in total.) The player pulls the box to point $8$. The player goes to point $7$. ($1$ move in this step. $8$ moves in total.) The player moved through $8$ edges in total and achieved the goal. So you output “Vegetable fallleaves” in the first line. As $8$ can be shown to be the minimum moves required to achieve the goal, you output “8” in the second line.官方中文