题号：NC213447
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
Mr.Banana and Kazuya are well known philosophers in New Nippori. Van, the king of New Nippori, can’t administer the empire without them, so he give the title of left and right guardian to them.
Because of the different politics, they are in the opposite sides. New Nippori has morning meeting every day and Van needs to design two routes so that Mr.Banana and Kazuya can participate in morning meeting. What makes things unmanageable is that if one road (not including two end points)belongs to both Mr.Banana’s and Kazuya’s route, they will wrestling with each other.
Generally, New Nippori is consist of n cities and m bidirectional roads without selfloops and there is at most one road connect any two cities. Mr.Banana lives in city 1 and Kazuya lives in city 2. There are two limosines in city n and n − 1, which they should get on to the morning meeting. More formally:
Because of the different politics, they are in the opposite sides. New Nippori has morning meeting every day and Van needs to design two routes so that Mr.Banana and Kazuya can participate in morning meeting. What makes things unmanageable is that if one road (not including two end points)belongs to both Mr.Banana’s and Kazuya’s route, they will wrestling with each other.
Generally, New Nippori is consist of n cities and m bidirectional roads without selfloops and there is at most one road connect any two cities. Mr.Banana lives in city 1 and Kazuya lives in city 2. There are two limosines in city n and n − 1, which they should get on to the morning meeting. More formally:
- if a road is in Mr.Banana’s route then it can’e be in Kazuya’s route and vice versa.
- if Mr.Banana should get on the limosine in city n while Kazuya should get on the limosine in city n − 1.
输入描述:
First line is an integer T(T ≤ 100), the number of the test cases. In each test case, there are two numbers n, m(4 ≤ n ≤ 2000, 0 ≤ m ≤ 10000),the number of cities and roads. Then following m lines, each line contains two integers u, v which means there is a road between city u and city v. It’s guaranteed there are at most 10 test cases that n > 100 or m > 1000.
输出描述:
Print a line "Case #x: "where x is the number of test case at the beginning of each case. If Van can design such two routes that not contains any same road, print "Banana and kazuya won’t be angry! else print "Van is in a dilema!".
示例1
备注:
In the first sample, one possible way in shown in the following picture:In the first sample, one possible way in shown in the following picture:In the third sample, there is no such way.
