Chef Thanos Wants Perfect Balance

Chef Thanos has an undirected simple graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges (numbered $1$ through $M$). For each valid $i$, the $i$-th edge connects vertices $u_i$ and $v_i$. Chef Thanos wants to colour the edges in red and green so that the graph would be perfectly balanced, which means that for each vertex, the number of red edges incident to it must be equal to the num