← 返回题目列表

Codeforces · 1210/A

A. 阿纳迪和多米诺

中文机器翻译题面 查看原题

阿纳迪有一组多米诺骨牌。每张多米诺骨牌都有两部分,每一部分都包含一些点。对于每个 $$$a$$$ 和 $$$b$$$ 使得 $$$1 \leq a \leq b \leq 6$$$,恰好存在一张多米诺骨牌,其一半上有 $$$a$$$ 点,另一半上有 $$$b$$$ 点。该套装包含 $$$21$$$ 多米诺骨牌。这是他的集合的精确说明:

此外,Anadi 有一个无向图,没有自环和多重边。他想选择一些多米诺骨牌并将它们放置在该图的边缘上。每种类型他最多可以使用一张多米诺骨牌。每条边最多可以容纳一张多米诺骨牌。没有必要在图的每条边上都放置多米诺骨牌。

将多米诺骨牌放在边缘时,他也会选择其方向。换句话说,任何放置的多米诺骨牌的一半必须指向边缘的一个端点,另一半必须指向另一个端点。有一个问题:如果多米诺骨牌的多半都指向同一个顶点,那么每一半都必须包含相同数量的点。

阿纳迪最多可以在他的图的边缘放置多少张多米诺骨牌?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 7$$$, $$$0 \leq m \leq \frac{n\cdot(n-1)}{2}$$$) — 图中的顶点数和边数。

接下来的 $$$m$$$ 行每行包含两个整数。第 $$$i$$$ 行中的整数是 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$),表示存在一条连接顶点 $$$a_i$$$ 和 $$$b_i$$$ 的边。

该图可能已断开连接。然而,可以保证该图不包含任何自环,并且任何一对顶点之间最多有一条边。

输出

输出一个整数,表示 Anadi 可以在图的边缘放置的多米诺骨牌的最大数量。

示例

输入 #1

4 4
1 2
2 3
3 4
4 1

输出 #1

4

输入 #2

7 0

输出 #2

0

输入 #3

3 1
1 3

输出 #3

1

输入#4

7 21
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

输出#4

16

注意

这是第一个示例测试中 Anadi 图表的说明:

这是在多米诺骨牌的每个边缘上放置多米诺骨牌的方法之一:

请注意,每个顶点都面临着具有相同点数的多米诺骨牌的一半。例如,指向顶点 $$$1$$$ 的所有半部分都有三个点。