CF1210A.Anadi and Domino

Anadi 有一套多米诺骨牌。每张多米诺骨牌有两部分，每部分上有若干点数。对于每一组 $a$ 和 $b$，满足 $1 \leq a \leq b \leq 6$，恰好有一张骨牌，一半上有 $a$ 个点，另一半上有 $b$ 个点。这套骨牌一共有 $21$ 张。下面是这套骨牌的示意图：

此外，Anadi 有一个无向图，图中没有自环和重边。他想选择一些骨牌，放在图的边上。每种骨牌最多只能用一次，每条边最多只能放一张骨牌。并不是每条边都必须放骨牌。

当在一条边上放置骨牌时，还可以选择骨牌的方向。也就是说，骨牌的一半朝向这条边的一个端点，另一半朝向另一个端点。有一个限制：如果有多张骨牌的某一半朝向同一个顶点，那么这些骨牌的这一半上必须有相同数量的点。

Anadi 最多能在图的边上放多少张骨牌？

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 7$，$0 \leq m \leq \frac{n\cdot(n-1)}{2}$），表示图中有 $n$ 个顶点和 $m$ 条边。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a, b \leq n$，$a \neq b$），表示有一条边连接顶点 $a_i$ 和 $b_i$。

图可能是不连通的。保证图中没有自环，每对顶点之间至多有一条边。

输出一个整数，表示 Anadi 最多能在图的边上放多少张骨牌。

下面是第一个样例测试中 Anadi 的图示意：

下面是其中一种在每条边上放置骨牌的方式：

注意，每个顶点朝向它的骨牌的一半上的点数都相同。例如，所有朝向顶点 $1$ 的骨牌的一半上都有三个点。

由 ChatGPT 4.1 翻译