Školjka

U jednom gradu je $M$ ulica i $N$ trgova, pri čemu su $M$ i $N$ prirodni brojevi takvi da je $M > N$. Svaka ulica povezuje dva trga i ne prolazi kroz druge trgove. Građani žele promijeniti izgled grada. Ove godine svaka će ulica biti po prvi put obojena crveno ili plavo. Dogovoreno je da se svake godine odabere jedan trg, te svim ulicama koje vode do tog trga istovremeno promijeni boja iz plave u crvenu i obratno. Dokaži da građani mogu odabrati boje ulica tako da se nikad u budućnosti ne može dogoditi da sve ulice budu iste boje.