The answer can be quite long ;)

What's the problem with D? It has two different solutions, one mathematical and one "straight-forward" without any math. So everyone should be happy :)

Вряд ли они будут final. У жюри кривое решение по третьей задаче (по крайней мере, куча правильных решений не зааксептилась, в том числе моё и Petr'а). Есть подозрение, что они не выбирают минимум в случае, когда есть несколько вариантов всё закрасить (а учитывая из рандомные тесты, такое случается довольно редко). Так что ждём rejudge. Свою систему они может и поправили, а вот писать несколько решений жюри так и не научились.

It appears that jury solution for 3rd problem is incorrect (or they have some mistakes in judging). So let's wait for rejudge.

You can resubmit solution after hack (if you haven't locked it already). So MBabin noticed that his solution is hacked, fixed bug and submitted new version.

Well, if you look at standings you can easily understand that O(m*m) will definitely fail, since a lot of people have TLE. It can be solved faster. The main observation is that if the required edges exist then there is an odd cycle and all edges in answer belong to this cycle. So the first thing to do is to find some odd cycle with DFS. Then you can delete this cycle from graph. If the resulting graph is not biparate, then answer is zero. Otherwise you can run dfs from each of the nodes on cycle marking the colors of nodes. The goal is to understand which cycle nodes have the same color and which opposite. So, you will get some statements like "Nodes x and y of cycle have the same color" or "Nodes x and y of cycle have the opposite color". Obviously each statement is equivalent to statement "Edge to be removed is on segment [x,y] of cycle" or "Edge to be removed is on segment [y,x] of cycle" (depending on (y - x) % 2). Number of statements is linear because they are generated by DFS, so we have problem to find which cycle edges are on all generated segments of cycle, this problem can be solved by usual methods (sorting etc.). I don't know if this problem can be solved in a less complicated way, but even this solution can be coded on contest.
PS: sorry for my terrible english.