#!/bin/python3

import math
import os
import random
import re
import sys


from collections import defaultdict


def _compute_edges_and_n_nodes(visit_node: int, children: dict, visited: set) -> (int, int):
    """
    Returns how many edges can remove this subtree and how many nodes it contains
    """
    # As children dict is bidirectional, we have to add nodes to visit in order to
    # avoid eternal loop
    visited.add(visit_node)
    
    # Exit case: Node is leaf, so it can not be a forest for its own
    if not len(children[visit_node]):
        return (0, 1)
        
    # We start counting nodes at 1 as we are assuming current node
    edges_to_remove, n_nodes = 0, 1
    for child in children[visit_node]:
        if child in visited:
            continue
        child_edges_to_remove, child_n_nodes = _compute_edges_and_n_nodes(child, children, visited)
        edges_to_remove += child_edges_to_remove
        n_nodes += child_n_nodes
        
    # If subtree is even, we add 1 edge to remove
    if not n_nodes % 2:
        edges_to_remove += 1
    return edges_to_remove, n_nodes


# Complete the evenForest function below.
def evenForest(t_nodes, t_edges, t_from, t_to):
    chldren = defaultdict(list)
    for n_from, n_to in zip(t_from, t_to):
        chldren[n_from].append(n_to)
        chldren[n_to].append(n_from)
    
    # We substract 1 to number of edges to remove because we don't want to count root
    return _compute_edges_and_n_nodes(1, chldren, set())[0] - 1


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t_nodes, t_edges = map(int, input().rstrip().split())

    t_from = [0] * t_edges
    t_to = [0] * t_edges

    for i in range(t_edges):
        t_from[i], t_to[i] = map(int, input().rstrip().split())

    res = evenForest(t_nodes, t_edges, t_from, t_to)

    fptr.write(str(res) + '\n')

    fptr.close()