you are given a treea simple connected graph with no cycles the tree has n nodes numbered from 1 to n and is rooted at node 1 find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of nodes constraints 2 2 100 note the tree input will be such that it can always be decomposed into components containing an even number of nodes pylint disableinvalidname dfs traversal pylint disableredefinedoutername ret 1 visitedstart true for v in treestart if v not in visited ret dfsv if ret 2 0 cuts appendstart return ret def eventree dfs1 if name main n m 10 9 tree defaultdictlist visited dictint bool cuts listint count 0 edges 2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8 for u v in edges treeu appendv treev appendu eventree printlencuts 1 pylint disable invalid name dfs traversal pylint disable redefined outer name 2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8 on removing edges 1 3 and 1 6 we can get the desired result 2
from collections import defaultdict


def dfs(start: int) -> int:
    
    
    ret = 1
    visited[start] = True
    for v in tree[start]:
        if v not in visited:
            ret += dfs(v)
    if ret % 2 == 0:
        cuts.append(start)
    return ret


def even_tree():
    
    dfs(1)


if __name__ == "__main__":
    n, m = 10, 9
    tree = defaultdict(list)
    visited: dict[int, bool] = {}
    cuts: list[int] = []
    count = 0
    edges = [(2, 1), (3, 1), (4, 3), (5, 2), (6, 1), (7, 2), (8, 6), (9, 8), (10, 8)]
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    even_tree()
    print(len(cuts) - 1)