if there are m even pairs then the answer is always zero. If there are odd pairs then the first intuition must come is that what if I remove one pair. so in a pair of (x,y) total contribution of x is (1(for y) + other neighbors) and for y ((1(for x) + other neighbors)). now there are 3 possibilities to remove a pair. 1.what if I remove x. 2.what if I remove y. 3.what if I remove both x and y.

for every (x,y) atleast one of the above possibilities gives even number of remaining pairs.

among these 3 possibilities check which one gives even number of remaining pairs and among them calculate the minimum. Likewise check for all possibilities of m pairs.

My solution:https://mirror.codeforces.com/contest/1711/submission/165671567