RU-SPB 2008 Problem 117

There are $10000$ cities in country, and roads between some cities. Every city has $<100$ roads. Every cycle route with odd number of road consists of $\geq 101$ roads. Prove that we can divide all cities in $100$ groups with $100$ cities, such that every road leads from one group to other.