Consider the answer of different cases:

**When M is even, obviously the answer is 1.**

**When M is odd, the answer is at least 2.**

In this case, if there is a vertex with odd degrees, just divide it into set 2 and others into set 1. So set 2 contains no edges and set 1 contains odd-odd=even edges. So the answer is 2.

The last case is that M is odd and all vertices have even degrees.

First its answer is not 2.

If we try to divide it into 2 sets, let’s name the number of edges in set 1 and set 2 A and B, and name the number of remaining edges C. Because all degrees are even, 2A+C and 2B+C are even, too. So we got C is even. When C is even, A+B=M-C is odd, so either A is odd or B is. This doesn’t meet the constraints.

**So for the rest cases the answer is at least 3**, and we can soon find that answer is 3.

The solution is find any of the edge, assume it connect u and v, so we divide u and v into set 2 and set 3, and all other vertices into set 1. In this case there are \mathrm{degree}(u) + \mathrm{degree}(v)-1 edges belonging to no sets. This is odd so the number of edges in set 1 is even.