def treeLength(tree, node, count):
    if tree.get(node):
        for n in tree[node]:
            count = treeLength(tree, n, count + 1)
    return count

def evenForest(t_nodes, t_edges, t_from, t_to):
    graph = {}
    for i in range(t_edges):
        if t_to[i] in graph:
            graph[t_to[i]].append(t_from[i])
        else:
            graph[t_to[i]] = [t_from[i]]
    count = 0
    for e in graph:
        for n in graph[e]:
            length = treeLength(graph, n, 1)
            if not length % 2:
                count += 1
    return count

#!/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()

<?php

function evenForest($t_nodes, $t_edges, $t_from, $t_to) {
    $graph = [];
    // Initialize graph
    for ($i = 1; $i <= $t_nodes; $i++) {
        $graph[$i] = [];
    }

    // Build adjacency list
    for ($i = 0; $i < count($t_from); $i++) {
        $graph[$t_from[$i]][] = $t_to[$i];
        $graph[$t_to[$i]][] = $t_from[$i];
    }

    // Array to store the size of each subtree
    $subtreeSize = array_fill(1, $t_nodes, 0);

    function dfs($node, $parent, &$graph, &$subtreeSize) {
        $subtreeSize[$node] = 1; // Include the node itself
        foreach ($graph[$node] as $neighbor) {
            if ($neighbor != $parent) {
                $subtreeSize[$node] += dfs($neighbor, $node, $graph, $subtreeSize);
            }
        }
        return $subtreeSize[$node];
    }

    // Start DFS from node 1 (arbitrary choice for the root)
    dfs(1, -1, $graph, $subtreeSize);

    $removableEdges = 0;

    // Count removable edges
    for ($i = 2; $i <= $t_nodes; $i++) {
        if ($subtreeSize[$i] % 2 == 0) {
            $removableEdges++;
        }
    }

    return $removableEdges;
}

// Example usage:
$t_nodes = 10;
$t_edges = 9;
$t_from = [2, 3, 4, 5, 6, 7, 8, 9, 10];
$t_to = [1, 1, 2, 2, 3, 3, 4, 4, 5];

echo evenForest($t_nodes, $t_edges, $t_from, $t_to); // Output should be 2

?>

using Node_t = int;
using Nodes_t = std::vector<::Node_t>;
using NodesQueue_t = std::queue<::Node_t>;
using NodesMap_t = std::unordered_map<::Node_t, ::Nodes_t>;

constexpr Node_t nodeRoot{1};
constexpr Node_t nodeDummy{0};

bool IsValidTreeCut(
    ::NodesMap_t &,
    ::Node_t const,
    ::Node_t const  
);

bool IsNodesCountEven(
    ::NodesMap_t &,
    ::Node_t const
);

int evenForest(
    ::Node_t const nodesCount,
    ::Node_t const edgesCount,
    ::Nodes_t const & nodesFrom,
    ::Nodes_t const & nodesTo
){
    using namespace std;
    auto nodeToNeighbours{::NodesMap_t{}};
    nodeToNeighbours[::nodeDummy] = ::Nodes_t{};
    for(size_t idx{0}; idx < nodesFrom.size(); ++idx){
        nodeToNeighbours[nodesFrom.at(idx)].emplace_back(nodesTo.at(idx));
        nodeToNeighbours[nodesTo.at(idx)].emplace_back(nodesFrom.at(idx));
    }
    auto qBfs{::NodesQueue_t{}};
    auto nodesVisited{vector<bool>(nodeToNeighbours.size(), false)};
    qBfs.push(::nodeRoot);
    nodesVisited.at(::nodeRoot) = true;
    nodesVisited.at(::nodeDummy) = true;
    auto nodeCurrent{numeric_limits<::Node_t>::max()};
    auto cutsCount{0};
    while(!qBfs.empty()){
        nodeCurrent = qBfs.front();
        qBfs.pop();
        for(auto const nodeNext: nodeToNeighbours.at(nodeCurrent)){
            if(nodesVisited.at(nodeNext)){
                continue;
            }
            qBfs.push(nodeNext);
            nodesVisited.at(nodeNext) = true;
            if(::IsValidTreeCut(nodeToNeighbours, nodeCurrent, nodeNext)){
                ++cutsCount;
            }
        }
    }
    return cutsCount;
}

bool IsValidTreeCut(
    ::NodesMap_t & nodeToNeighbours,
    ::Node_t const nodeParent,
    ::Node_t const nodeNewRoot 
){
    using namespace std;
    auto & nodesNeighboursA{nodeToNeighbours.at(nodeNewRoot)};
    auto nodeParentIter{find(begin(nodesNeighboursA), end(nodesNeighboursA),
        nodeParent)};
    if(nodeParentIter == end(nodesNeighboursA)){
        return false;
    }
    *nodeParentIter = ::nodeDummy; 
    auto & nodesNeighboursB{nodeToNeighbours.at(nodeParent)};
    auto nodeNewRootIter{find(begin(nodesNeighboursB), end(nodesNeighboursB),
        nodeNewRoot)};
    if(nodeNewRootIter == end(nodesNeighboursB)){
        return false;
    }
    *nodeNewRootIter = ::nodeDummy;
    if(::IsNodesCountEven(nodeToNeighbours, nodeNewRoot)){
        return true;
    }
    *nodeParentIter = nodeParent;
    *nodeNewRootIter = nodeNewRoot;
    return false;
}

bool IsNodesCountEven(
    ::NodesMap_t & nodeToNeighbours,
    ::Node_t const nodeNewRoot
){
    using namespace std;
    auto qBfs{::NodesQueue_t{}};
    auto nodesVisited{vector<bool>(nodeToNeighbours.size(), false)};
    qBfs.push(nodeNewRoot);
    nodesVisited.at(nodeNewRoot) = true;
    nodesVisited.at(nodeDummy) = true;
    auto nodeCurrent{numeric_limits<::Node_t>::max()};
    size_t nodesCount{1};
    while(!qBfs.empty()){
        nodeCurrent = qBfs.front();
        qBfs.pop();
        for(auto const nodeNext: nodeToNeighbours.at(nodeCurrent)){
            if(nodesVisited.at(nodeNext)){
                continue;
            }
            qBfs.push(nodeNext);
            ++nodesCount;
            nodesVisited.at(nodeNext) = true;   
        }
    }
    return nodesCount % 2 == 0;
}