The last contest's D question, I came up to a solution which got accepted by I do not have the proof the solution. What I did was, First I did a DFS to give colours to the node(here colours means the parity like in bipartite graphs) and maintain two sets for even parity and odd parity. Now, if i came up to any adjacent nodes which have same colour assigned, I just removed any node from the set, given that both nodes are in the set. Now for the answer, I checked whether the bigger set have atleast K / 2 elements or not. If yes, the print the answer and exit and if not, I did another dfs to find cycles, and print it if its length is atmax k.
Anyone with some proof or willing to discuss or even hack it will sure help me. Thanks.
