PROBLEM LINK:
DIFFICULTY
EASY
PREREQUISITES
Graph Theory, Bipartite Graph, Two colouring, DFS
(Alternate Solution) Gauss Elimination, Minimum Spanning Tree, Finite Field Arithmetic  especially GF(2)
PROBLEM
Given a graph, houses as nodes and roads as edges, you can warp some edges out of a restricted set of edges. Warping an edge means the two vertices it joins are merged and all the existing edges are extended to this new vertex.
This may result in some edges becoming self loops. Unless these self loops can be warped, they should not be formed.
Your aim is to make the graph bipartite.
EXPLANATION
The setter and the tester use two very different approaches to solve the problem.
TESTERS APPROACH
Let us look at this approach first, because of its simplicity!
Ignore the warpable edges. Don’t warp them yet, but consider the graph without any of edges that can be warped. Let this graph be called A.
Try to find a two colouring of A. Now, some of the warpable edges can be warped to get a bipartite graph if and only if it was possible to find a two colouring of A. This result is because

If A is not bipartite, since no edges of A can be warped and self loops are not ignored, A cannot be bipartite finally after warping any of the remaining edges.

If A is bipartite, then we warp those edges that are connecting the vertices of the same colour. This way, we will never introduce self loops, the the final graph will also be bipartite  since we preserved only those edges that connected vertices of different colour.
The only remaining trick is to find whether A has a two colouring.
This can be done by doing a DFS on the graph and trying to two colour it arbitrarily. If ever an edge is encountered which connects to a vertex previously coloured, and whose colour is same as the colour you are about to assign to the current vertex; then you have found a necessary and sufficient witness to the non bipartiteness of the graph.
SETTERS APPROACH
The setter used a very complicated technique, which relies upon the following axiom:
For a graph to be bipartite, all the cycles must be of even length.
We can construct a system of linear equations in GF(2). Consider the set of binary variables E_{W} representing all the warpable edges. If a variable is 1, it means the edge is not warped, and vice versa.
We can construct equations over these variables, where each equation refers to a cycle in the graph. Each equation should evaluate to {0, 1} based on whether after warping a set of edges, there should remain even or odd number of edges from the set of warpable edges.
Since the number of cycles can be exponential in a graph, we must consider a polynomial number of cycles which can be linearly combined (that is symmetric difference of their edge sets taken) to get all the other cycles. One such set of cycles can be achieved as follows
 Consider a minimum spanning tree of the graph
 Add an edge and consider the unique cycle hence created
 Repeat the other step by deleting the previously added edge and adding a new one each time
This gives O(E) cycles to consider, whose linear combination (addition in GF(2)) produces all the other cycles.
What remains is to verify whether the system of equations hence built has a valid solution or not. This can be done via Gaussian Elimination.
Gaussian Elimination can be applied to ensure whether it is possible to have even number of edges unwarped for cycles that have even number of unwarpable edges otherwise, and viceversa.
SETTERS SOLUTION
Can be found here
TESTERS SOLUTION
Can be found here