SP16483 LUCKY - Lucky Cities

John 最近来到罗马尼亚参加东南欧区域竞赛。他以前从未去过罗马尼亚，因此罗马尼亚人为他安排了一次观光旅行。这次旅行包括几个罗马尼亚的城市，每个城市只访问一次。旅行从一个城市开始，然后根据导游的安排访问其他城市，最终回到出发的城市。 整个罗马尼亚有 $N$ 个城市，编号从 $1$ 到 $N$，以及 $M$ 条双向道路。每条道路连接两个不同的城市。John 的一次观光路线用 $c_1, c_2, \ldots, c_n$ 表示，其中每个 $c_i$ 是罗马尼亚的一个城市。在这次旅行中，所有城市 $c_i$ 必须不同，相邻的城市 $c_i$ 和 $c_{i+1}$ 之间必须有道路连接，同时 $c_n$ 和 $c_1$ 之间也要有道路连接。 作为一个喜欢奇数的人，John 希望他的旅行里访问的城市数量是奇数。组织者已经提供了所有可能的包含奇数个城市的旅行路线。 对于城市的居民来说，他们希望 John 能够去到他们的城市。因此，如果至少有一条包含某个城市的旅行路线，该城市就被称为幸运城市。你的任务是计算罗马尼亚有多少个这样的幸运城市。

第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $N$ 和 $M$，用空格分隔。接下来的 $M$ 行每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条道路连接的城市编号。

输出应有 $T$ 行，每行对应一个测试用例的结果。

- $1 \le T \le 100$ - $1 \le N \le 1000$ - $0 \le M \le 10,000$ - $1 \le a_i, b_i \le N, \quad a_i \neq b_i$ **本翻译由 AI 自动生成**