n,m=map(int,input().split())
if m == 0:
    print(4+(n%2))
else:
    inc=[0]*(n+1)
    for _ in range(m):
        u,v =map(int,input().split())
        inc[u] += 1
        inc[v] += 1
    p=n%2
    if p==0:
        c=0
        for x in inc[1:]*2:
            if c>1: p=1
            if x: c=0
            else: c +=1
        
        
    q=0
    for x in inc:
        if x and x != 2: q=1
    if p==q==0:p=1
    print(p+q+3)