SP2878 KNIGHTS - Knights of the Round Table

题目描述

### 题目大意 有 $n$ 个骑士经常举行圆桌会议,商讨大事。每次圆桌会议至少有 $3$ 个骑士参加,且相互憎恨的骑士不能坐在圆桌的相邻位置。如果发生意见分歧,则需要举手表决,因此参加会议的骑士数目必须是大于 $1$ 的奇数,以防止赞同和反对票一样多。知道骑士之间相互憎恨的关系后,请你帮忙统计有多少骑士参加不了任意一个会议。

输入格式

**本题包含多组数据。** 对于每组数据, 第一行为两个整数 $n$ 和 $m$。 接下来 $m$ 行每行两个整数 $k_1$ 和 $k_2$,表示骑士 $k_1$ 和 $k_2$ 相互憎恨。 $n=m=0$ 为数据末尾的标记,无需处理这组数据。

输出格式

对于每组数据,输出一行一个整数,表示无法参加任何会议的骑士数量。 感谢@hicc0305 提供的翻译

说明/提示

$1\leq n \leq 10^3$,$1\leq m\leq10^6$。保证 $1\leq k_1,k_2\leq n$。 $\small{\text{Statement fixed by @Starrykiller.}}$