This problem was actually proposed in one of the latest Codeforces rounds. It is obvious that the Greedy algorithm is not good enough. The trick is to make a bipartite graph with the X-s coordinates of the points in one set and the Y-s in the other. Then we can add undirected edges from any x from the first set to any y from the other set as long as point (x,y) exists in input. If our resulting graph is eulerian, it's obvious that our problem is done, because we can color edges ( that are actually points from the input ) in white-red-white-red uniformly across the eulerian cycle we have. The problem is if we have nodes with odd degree. That can be really nice solved by adding 2 more nodes, one where we add edges between him and the x's nodes with odd degree and other node where we add between him and the y's nodes with odd degree. The question is : What if these 2 other nodes have odd degree now? We can easily notice that either both have odd degree , either both have even degree, so it is enough to add an edge between them in case the degrees are odd. And we have an eulerian graph. In this way, after coloring the eulerian path as I sad, every node has an equal number of white and red edges adiacent to him, so if we delete our fake 2 nodes we used to help us, the difference of colors is at most 1, and the problem is solved. 

Am aflat acum ca le-a intrat unora ci solutia asta, deci cred ca am gresit eu ceva. Oricum e o solutie cu 0 structuri de date, care cica e smen.

La problema Disconnect mergea o idee mult mai draguta cu liniarizare dfs si smenul lui mars pe aib. Am bagat asta in concurs si am luat doar 80. era mult mai tare daca intra si solutia pentru a incuraja solutii originale, nu implementare de heavy Path :p

Ce nu zice in ziua de azi un elev inainte de un concurs IA :
" Sper sa nu fac prost si sa nu-mi scad ratingul "

horatiu11 :
vezi ca nu te opresti cand incepi deja sa ai elemente diferite pe linia respectiva cand construiesti matricea d.
gen, daca ai linia ta :
11122212211
tu actualizezi solutia pt ultimul 1, penultimul, dar cand dai peste 2 trebuie sa iesi din for, nu sa continui 

Ideea lui ctlin04 e geniala.
Tine-ti stiva ca un vector de char si afiseaza-l deodata si ia 100 p. 

LE : A iesit cu parsare! 

Eu am facut problema cu paduri de multimi disjuncte si cu o matrice cu niste biti si ideea e ca iau TLE pe testele 6 si 7.
Am o intrebare : Nu se poate lua 100 si cu solutii fara grafuri? Am incercat sa fac si o parsare care da roade , dar obtin Incorect pe testele de la 4 incolo.
Parsarea este aceasta :
Cod :
fin.getline(sir,25000);
aux=0;cnt=0;
for(poz=0;sir[poz];poz++)
            if(sir[poz]>='0' && sir[poz]<='9')
                aux=aux*10+sir[poz]-'0';
            else
             {
                 t[++cnt]=aux;
                 aux=0;
             }
        t[++cnt]=aux;
Imi puteti spune va rog ce gresesc aici sau, daca se poate sa-mi dati testul 4.
Multumesc anticipat!