Lanternlight Islands
A city has stations connected by bidirectional tunnels. There is exactly one simple path between every pair of stations.
Whenever a patrol route from station to station is active, every station and every tunnel on that path is illuminated. In particular, a route from a station to itself illuminates that station and no tunnel. An object remains illuminated as long as at least one active route contains it.
An illuminated region is a connected component of the subgraph formed by all illuminated stations and illuminated tunnels. Two illuminated stations belong to the same region only if they are connected using illuminated tunnels. If nothing is illuminated, the number of illuminated regions is .
Initially, there are no active routes. Process operations that add or remove routes. Each added route receives an identifier equal to the number of addition operations processed so far. After every operation, report the current number of illuminated regions.
Input
The first line contains two integers and (), the number of stations and operations.
Output
Print lines. After the -th operation, print the number of illuminated regions formed by all currently active routes.
Samples
Sample 1
Input
6 8 1 2 2 3 2 4 4 5 4 6 + 1 3 + 5 6 + 3 5 - 3 + 2 2 - 1 - 2 - 4
Output
1 2 1 2 2 2 1 0
The first two routes illuminate separate parts of the network. Route joins them, and removing it separates them again. Route consists only of station . After the final removal, no station or tunnel is illuminated.