Excuse me for my bad English.

My idea of the decision:  On each step we find a component with the greatest amount of the components of other color connected with it and we paint it. And so until then while all tops do not make one component.

The component is a set of tops between which it is possible to spend a way which is not passing on edges, connecting tops of different color.
Components are considered coherent if between any two tops taken from first and second will connect a way which is passing only through one edge, connecting multi-coloured tops. Such edges I named heavy.
  In realization it is ideas it is possible to use procedure of convolution the column, that is turns off a component in one top.

I cannot think up the test on which this decision gives the incorrect answer. Realization of the decision passes 4 tests (((. On the fifth Crash. ((
Tell please that in my idea incorrectly. Thanking you very much in advance.

Dlya vseh kto ploho znaet angliiskii:

Pomogite s ideey resheniya zadachi i s pyatym testom.

Moya ideya resheniya:
  Na kajdom shage nahodim komponent s naibol'shim kolichestvom svyazannyh s nim komponentov  drugogo cveta i krasim ego. I tak do teh por poka vse vershiny ne sostavlyayut odin komponent.
Komponent - eto mnojestvo vershin mejdu kotorymi mojno provodit' put', ne prohodyaschiy po rebram, soedinyayuschim vershiny raznogo cveta.
Komponenty schitayutsya svyaznymi, esli mejdu lyubye dve vershiny, vzyatye iz pervogo i vtorogo budet soedinyat' put', prohodyaschiy tol'ko cherez odno rebro, soedinyayuschee raznocvetnye vershiny. Takie rebra ya nazyval tyajelymi.
  V realizacii eto idei mojno ispol'zovat' proceduru svertki grafa, to est' svorachivaet komponent v odnu vershinu.

Ya ne mogu pridumat' test, na kotorom eto reshenie daet nevernyy otvet. Realizaciya resheniya prohodit 4 testa(((. na pyatom Crash.((
Skajite pojaluysta chto v moey idee neverno. Zaranee blagodaryu.

I failed WA5 when I used wrong variable for the output of vertex node. Your idea was first that came into my head, but it's wrong...

Try this test:
11 10
J E E J J J J J J J J
1 2
1 3
2 4
2 5
2 6
2 7
3 8
3 9
3 10
3 11

The answer is 2, but your degree-greedy algo will give 3