import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[0 for _ in range(9)] for _ in range(9)]
for _ in range(m):
a,b=input().split()
a=ord(a)-ord('A')
b=ord(b)-ord('A')
g[a][b]=1
g[b][a]=1
from functools import lru_cache
@lru_cache(None)
def solve(mask,last):
if mask==(1<<n)-1:
return 0
ret=100
for i in range(n):
if (mask>>i)&1:
continue
ret=min(ret,solve(mask|(1<<i),i)+ (1 if g[last][i] else 0))
return ret
ans=0
for i in range(n):
ans=max(ans,n-1-solve(1<<i,i))
print(ans)
aW1wb3J0IHN5cyAKc3lzLnNldHJlY3Vyc2lvbmxpbWl0KDEwKio3KQpuLG09bWFwKGludCxpbnB1dCgpLnNwbGl0KCkpCmc9W1swIGZvciBfIGluIHJhbmdlKDkpXSBmb3IgXyBpbiByYW5nZSg5KV0KZm9yIF8gaW4gcmFuZ2UobSk6CiAgICBhLGI9aW5wdXQoKS5zcGxpdCgpCiAgICBhPW9yZChhKS1vcmQoJ0EnKQogICAgYj1vcmQoYiktb3JkKCdBJykKICAgIGdbYV1bYl09MQogICAgZ1tiXVthXT0xCgpmcm9tIGZ1bmN0b29scyBpbXBvcnQgbHJ1X2NhY2hlCkBscnVfY2FjaGUoTm9uZSkKZGVmIHNvbHZlKG1hc2ssbGFzdCk6CiAgICBpZiBtYXNrPT0oMTw8biktMToKICAgICAgICByZXR1cm4gMAogICAgcmV0PTEwMAogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgaWYgKG1hc2s+PmkpJjE6CiAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgcmV0PW1pbihyZXQsc29sdmUobWFza3woMTw8aSksaSkrICgxIGlmIGdbbGFzdF1baV0gZWxzZSAwKSkgCiAgICByZXR1cm4gcmV0IAphbnM9MApmb3IgaSBpbiByYW5nZShuKToKICAgIGFucz1tYXgoYW5zLG4tMS1zb2x2ZSgxPDxpLGkpKQpwcmludChhbnMpCg==