import sys
from sys import stdin
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, stdin.readline().split())
    in_degree = [0] * (N + 1)
    out_degree = [0] * (N + 1)
    adj_undirected = [[] for _ in range(N + 1)]  # For connected components

    for _ in range(M):
        u, v = map(int, stdin.readline().split())
        out_degree[u] += 1
        in_degree[v] += 1
        adj_undirected[u].append(v)
        adj_undirected[v].append(u)  # undirected

    # Compute d_initial for each node
    d_initial = [0] * (N + 1)
    sum_d_initial = 0
    for u in range(1, N + 1):
        d = out_degree[u] - in_degree[u]
        d_initial[u] = d
        sum_d_initial += abs(d)

    # Check for open scenario
    max_d = max(d_initial)
    min_d = min(d_initial)
    has_positive = max_d >= 1
    has_negative = min_d <= -1

    K_closed = float('inf')
    if sum_d_initial % 2 == 0:
        K_closed = sum_d_initial // 2

    K_open = float('inf')
    if has_positive and has_negative:
        new_sum = sum_d_initial - 2
        if new_sum >= 0 and new_sum % 2 == 0:
            K_open = new_sum // 2

    K_degree = min(K_closed, K_open)

    # Compute connected components
    visited = [False] * (N + 1)
    C = 0
    for u in range(1, N + 1):
        if not visited[u]:
            C += 1
            stack = [u]
            visited[u] = True
            while stack:
                node = stack.pop()
                for neighbor in adj_undirected[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)

    K_connect = max(0, C - 1)

    answer = max(K_degree, K_connect) if K_degree != float('inf') else float('inf')

    if answer == float('inf'):
        print(-1)
    else:
        print(answer)

if __name__ == '__main__':
    main()