没搞懂输入数据格式搞成这么奇怪的格式是为什么，代码浪费时间去处理这种奇怪的输入格式，没看出来有什么意义

'''
每一个点拆成出点和入点
枚举源点S和汇点T，S入点和出点间连边权无穷大的有向边，T入点和出点之间连边权无穷大的有向边
其他点的入点和出点之间连接边权是1的有向边
原图中已经有的无向边转成两条有向边，有向边起点对应的点的出节点向有向边终点的入节点连接边权
是1的有向边，求取S到T的最小割，割边一定都是除了源点和汇点之间的其他点的入点和出点之间的边
割边的数量就是最小割数值，也就是最少要删除多少条入点和出点之间的边，才能让S到T不连通
也就等价于是删除多少个S T以外的点，能够让S T不连通，枚举 S 和 T 找需要删除的点的最小个数
就是最后的答案

'''



from typing import List
from collections import deque
import sys


class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数，max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量，(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离，用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标，也称当前弧，用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化，记录每一个节点最后走的一条边，只要limit还没有减成0，已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了，另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉，不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路，就dfs把增广路都找到，把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow




while True:

    try:
        s = input()
        if s == '':
            continue
        ss = s.split()
        n, m = int(ss[0]), int(ss[1])
    except:
        break

    e = []
    for num_s in ss[2:]:
        a, b = map(int, num_s[1:-1].split(','))
        a, b = a + 1, b + 1
        e.append((a, b))

    while len(e) < m:
        s = input()
        ss = s.split()
        for num_s in ss:
            a, b = map(int, num_s[1:-1].split(','))
            a, b = a + 1, b + 1
            e.append((a, b))


    ans = n
    for S in range(1, n+1):
        for T in range(1, n+1):
            if S == T:
                continue

            edges = []
            for node in range(1, n+1):
                if node != S and node != T:
                    edges.append((node, node+n, 1))
                else:
                    edges.append((node, node+n, 0x7fffffff))

            for a, b in e:
                edges.append((a+n, b, 0x7fffffff))
                edges.append((b+n, a, 0x7fffffff))

            ans = min(ans, FortdFulkerson(edges, S, T, 2*n, len(edges)).getMaxFlow())

    print(ans)