SP10587 ENEM - Enemies

题目描述

在大都市中,帮派问题日益严重。身为帮派成员的人,通常都有几个仇敌。当这些敌人相遇时,总会想大打出手,从而使城市变得非常危险。这些帮派成员被称作斗士。 当地警察局收到匿名举报,称有一场大型斗士集会将在中央公园举行。但警察局长想知道是否有必要派警员去场地。他了解到,斗士只有在所有仇敌都在场的情况下才会主动攻击。如果有一个斗士不想打架,这次集会就会取消。此外,每次打架时,斗士只能与一个仇敌较量,而其他仇敌则会等待,因为他们都想单独击败对方。局长知道,只需要一个警察就能阻止两名斗士打斗。 基于上述信息以及这次集会上斗士之间的敌对关系,你的任务是告诉局长,这次集会是否会被取消。如果不会取消,局长还想知道,为了阻止打架,最少需要派多少名警察。

输入格式

每组测试数据由多行组成。第一行包含两个整数 $F$($1 \le F \le 10^5$)和 $R$($1 \le R \le 10^5$),分别表示斗士的数量和敌对关系的数量。斗士编号为从 $0$ 到 $F-1$ 的不同整数。接下来的 $R$ 行,每行包含两个整数 $A$ 和 $B$,表示斗士 $A$ 和斗士 $B$ 是敌人。可以假定每对敌对关系在每组测试数据中只出现一次,并且如果 $A$ 是 $B$ 的敌人,那么 $B$ 也是 $A$ 的敌人。输入以 $F = 0$ 和 $R = 0$ 结束。

输出格式

对每组测试数据输出一行。如果集会会被取消,则输出「The meeting will be canceled」;否则,输出防止打架所需的最少警察人数。 **本翻译由 AI 自动生成**