← 返回 openai 的题目列表Draw Paths / Strokes on a Set of Points
类型：online_judge
Problem: Minimum Strokes to Draw All Edges (Min Trails)
You are given an undirected graph where vertices are points and edges are line segments that must be drawn. A single “stroke” starts at any vertex and continuously traverses edges to draw them, with the constraint that each edge must be drawn exactly once overall. You may revisit vertices, but you may not traverse (draw) an edge more than once.
Compute the minimum number of strokes required to draw all edges.
Input (stdin)
First line: two integers n m (number of vertices and edges)
Next m lines: two integers u v (0-indexed) describing an undirected edge
Output (stdout)
Print one integer: the minimum number of strokes.
Constraints
1 <= n <= 2e5
0 <= m <= 2e5
Multi-edges may exist; ignore self-loops if present.
The graph may be disconnected.
Notes
For each connected component: if it has no edges, it needs 0 strokes.
Otherwise, the answer depends on how many odd-degree vertices the component has.
Sample Tests
Input:
3 2
0 1
1 2
Output:
1
Input:
4 2
0 1
2 3
Output:
2
Input:
4 3
0 1
1 2
2 0
Output:
1
Input:
5 4
0 1
1 2
2 3
3 4
Output:
1
Input:
6 3
0 1
0 2
0 3
Output:
2
Example
Input
3 2
0 1
1 2
Output
1