解答

def can_traverse_all_bridges(n, m, bridges): from collections import defaultdict, deque # 構建圖 graph = defaultdict(list) degree = defaultdict(int) for a, b in bridges: graph[a].append(b) graph[b].append(a) degree[a] += 1 degree[b] += 1 # 計算奇數度頂點的數量 odd_count = sum(1 for d in degree.values() if d % 2 != 0) # 如果奇數度頂點的數量不是0或2，則返回NO if odd_count != 0 and odd_count != 2: return "NO" # 檢查圖的連通性 def is_connected(): visited = set() start_node = next(iter(graph)) stack = [start_node] while stack: node = stack.pop() if node not in visited: visited.add(node) stack.extend(graph[node]) return len(visited) == len(graph) if not is_connected(): return "NO" return "YES" # 讀取輸入 import sys input = sys.stdin.read data = input().split() n = int(data[0]) m = int(data[1]) bridges = [] index = 2 for _ in range(m): a = int(data[index]) b = int(data[index + 1]) bridges.append((a, b)) index += 2 # 輸出結果 print(can_traverse_all_bridges(n, m, bridges))