12. Drump Dislikes Trump Too

单点时限: 2.0 sec

内存限制: 256 MB

在桥蓝国,有 (N) 座城市。由于桥蓝国总统 Drump 不支持发展陆路运输,城市和城市之间都是用双向航班来连接的。Tonald Drump,作为新一任的桥蓝国总统,对修改航班时刻表非常感兴趣。他每天都会做这样的事:

  • 选择一个城市;

  • 把该城市已经开通的航班全部取消,引入所有没有开通的航班。

比如说,5 号城市现在有直达 3 号城市和 4 号城市的航班,但没有直达 1 号和 2 号城市的,那么,在 Drump 进行了修改之后,从 5 号城市可以直达 1 号和 2 号,但不能直达 3 号和 4 号。

但这项改革并不是完全不好的。比如约纽时报就指出,可能会有那么一天,任意两个城市之间都有直达航班相连。

这真的有可能吗?写个程序帮忙算一算。

输入格式

输入第一行是一个整数 (K) ((K \leq 5)),表示数据组数。接下来是连续的 (K) 组数据。

每组数据的第一行含有一个整数 (N) ((2 \leq N \leq 1000)),表示城市的数量。方便起见,城市被编号为 (1) 到 (N) 的正整数。

第二行是一个整数 (M) ((0 \leq M \leq \frac{N \cdot (N-1)}{2})),表示已经拥有的航班数量。

接下来 (M) 行每行都是两个不同的整数,表示两个城市有直达航班相连。

对于约 50% 的数据,满足 (N \leq 100)。

输出格式

对于每组测试数据,输出一行,以 Case i: 开头。YES 表示能够达到目标,NO 表示不能。

样例

Input
3

2
0

3
2
1 2
2 3

4
2
1 3
2 4
Output
Case 1: YES
Case 2: NO
Case 3: YES

提示

为方便阅读,样例在每组数据之间增加了一个换行。

样例 1 解释:Drump 可以引入唯一的航班 1-2。

样例 2 解释:Drump 首先选择城市 1,1-2,1-4,2-4 都将建立起来。然后再选择城市 3,就达到了每两个城市之间都有航班的要求。

21 人解决,37 人已尝试。

26 份提交通过,共有 59 份提交。

5.2 EMB 奖励。

创建: 3 年,5 月前.

修改: 3 年前.

最后提交: 6 月,3 周前.

来源: COCI 2016/2017

题目标签