402373: GYM100739 G Old town

The city of Kaunas has an amazing history, and its old town reveals a lot of secrets. However, this does not amaze Informikas at most, who is keen on the structure of the city roads. The ancient roads connect all parts of the city, and the removal of any of them would make some parts of Kaunas unreachable from other parts (by the old roads). As Informikas is quite smart (he is a software developer), he understands that roads in past were much more reliable, which were built by orcs with huge hammers, with dragons flying around them... As a consequence, the old roads can not be removed or damaged in any way.

In the present times, Informikas is sure that everyone knows the Dijkstra's algorithm, and that is why a lot of new roads are constructed or removed. Those new roads are constructed by ordinary humans, and because of this they can not stand the test of time...

In Informikas's opinion, it is interesting to know the number of important roads after each construction or demolition. A road is called important if after the theoretical removal of it, the city would become disconnected (there would exist two parts of the city that do not have any path between them by the old or new roads).

The first line of the input contains n and m (1 ≤ n, m ≤ 10⁵) - the number of the city parts and the initial number of roads (either old or new).

The following m lines contain 3 integers each, a, b and c (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ c ≤ 1), showing the numbers of connected city parts by this road, and c = 1 if the road is new, and c = 0 if it is old. Two cities can not have more than one road in-between.

The following line contains an integer number of updates (constructions or demolitions), q (1 ≤ q ≤ 10⁵).

The following q lines contain 2 integers each, u and v (1 ≤ u, v ≤ n, u ≠ v). If the road between u and v exists, the line corresponds to the deletion of the road, and if not, then to the construction of the road between those cities.

On the first line print the number of important roads of the initial network.

On the following q lines print the numbers of important roads after each modification.

6 6
1 2 0
1 5 1
1 4 0
5 4 0
6 4 0
2 3 0
4
6 5
1 5
5 6
3 6

3
2
3
5
1