Inkopolis is the city in which Inklings live in, it can be regarded as an undirected connected graph with exactly $N$ vertices and $N$ edges between vertices. It is guaranteed that the graph doesn’t contain duplicated edges or self loops. Inklings can splatter a special type of colored ink to decorate the roads they live in. Inklings are capricious so they often change the color of the roads to celebrate the upcoming Splatfest.
The Splatfest lasts for exactly $M$ days, on each day Inklings will splatter ink on exactly one road, the color on this road will be coverd by the new color of the ink. At the end of each day, they wonder how many different colored regions are there in the Inkopolis. A colored region is a set of connected roads with same color, to be clear, two roads are in the same colored region if they have the same color and share a common vertex.