import sys sys.setrecursionlimit(1 << 25) from collections import defaultdict def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]); ptr +=1 M = int(input[ptr]); ptr +=1 A = [[0]* (N+1) for _ in range(N+1)] for _ in range(M): r = int(input[ptr]); ptr +=1 c = int(input[ptr]); ptr +=1 A[r][c] = 1 parent = {} def find(u): if parent[u] != u: parent[u] = find(parent[u]) return parent[u] def union(u, v): pu = find(u) pv = find(v) if pu != pv: parent[pu] = pv for r in range(1, N+1): for c in range(1, N+1): if A[r][c]: u = ('row', r) v = ('col', c) if u not in parent: parent[u] = u if v not in parent: parent[v] = v union(u, v) components = defaultdict(list) for u in parent: root = find(u) components[root].append(u) node_to_comp = {} for comp_id, comp in enumerate(components.values()): for u in comp: node_to_comp[u] = comp_id row_comp = {} col_comp = {} for u in parent: if u[0] == 'row': row_comp[u[1]] = node_to_comp[u] else: col_comp[u[1]] = node_to_comp[u] for i in range(1, N+1): if i not in row_comp: u = ('row', i) parent[u] = u node_to_comp[u] = len(components) row_comp[i] = len(components) components[len(components)] = [u] if i not in col_comp: u = ('col', i) parent[u] = u node_to_comp[u] = len(components) col_comp[i] = len(components) components[len(components)] = [u] adj = defaultdict(set) for r in range(1, N+1): for c in range(1, N+1): if A[r][c] == 0: cr = row_comp[r] cc = col_comp[c] adj[cr].add(cc) adj[cc].add(cr) from itertools import product comp_list = list(components.keys()) C = len(comp_list) min_total = float('inf') for mask in product([0,1], repeat=C): total = 0 for r in range(1, N+1): for c in range(1, N+1): if A[r][c] == 0: cr = row_comp[r] cc = col_comp[c] if mask[cr] == mask[cc]: total +=1 if total < min_total: min_total = total print(min_total) if __name__ == '__main__': main()