In the capital of Bytocja, a great cycling race is held every year. The city has $n$ locations, numbered from $1$ to $n$, connected by $m$ one-way roads. It is known that one can travel from location $1$ to any other location. Race participants start at a certain location $s$ and then move along the roads (following their directions) so as to finally return (after traversing at least one road) to the starting location $s$. Thus, the race route is $s = t_0, t_1, t_2, \dots, t_\ell = s$ (for $\ell \ge 1$), where for each $i$ ($1 \le i \le \ell$) there exists a road from location $t_{i-1}$ to location $t_i$.

To add some variety to the possible routes, the event organizers have obtained permission from the mayor to temporarily change the directions of some roads in the following way. The organizers can choose a sequence of pairwise distinct roads. Denoting the length of this sequence by $k$, for each $i$ ($1 \le i \le k$), the $i$-th chosen road must lead from location $z_{i-1}$ to location $z_i$. There are no additional restrictions on the locations $z_i$; in particular, they do not have to be distinct, and we do not require $z_0 = z_k$. Then, for the purposes of the race, the direction of each of these roads is changed, meaning that for each $i$ ($1 \le i \le k$), instead of the chosen road from $z_{i-1}$ to $z_i$, we now have a road from $z_i$ to $z_{i-1}$. If the organizers choose an empty sequence, nothing is changed.

The organizers are now wondering for how many starting locations $s$ there exists a race route starting and ending at $s$, assuming that after choosing the location $s$, they can temporarily change the directions of some roads in the manner described above. Let us call this value the number of allowed starting locations.

The organizers have received from the mayor a list of $q$ additional roads, one of which can be built for the purposes of the race. Therefore, they would like to determine, for each additional road, how many allowed starting locations there will be after building that road.

Your task is to determine the initial number of allowed starting locations, and also to determine, for each of the $q$ additional roads, the number of allowed starting locations after building that road.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 1\,000\,000$, $0 \le m \le 1\,000\,000$), representing the number of locations and the number of roads, respectively. The $i$-th of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), representing a road from location $a_i$ to location $b_i$. The next line of input contains a single integer $q$ ($0 \le q \le 1\,000\,000$), representing the number of additional roads. The $i$-th of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), representing an additional road from location $x_i$ to location $y_i$.

The city may contain more than one road connecting a pair of locations. There may also be roads connecting a location to itself. The mayor may also allow building a road between a pair of locations that is already connected. It is known that one can travel from location $1$ to any other location.

Output

The first line of output should contain the number of allowed starting locations without building any of the additional roads. The $i$-th of the next $q$ lines should contain the number of allowed starting locations after building the $i$-th additional road.

Examples

Input 1

5 5
1 2
2 3
3 4
2 4
4 5
3
1 3
4 5
1 5

Output 1

3
4
4
5

Note

The original layout of the roads is as follows:

Each of the locations 2, 3, 4 is an allowed starting location. If the organizers decided to change the direction of the road connecting locations 2 and 4, from each of the locations 2, 3, 4 one could trace a race route ending at the same location. The same goal could be achieved by changing the directions of the roads connecting 2 and 3, and 3 and 4 simultaneously.

In the case of building a road from location 1 to location 3, the layout would look as follows:

In this case, each of the locations 2, 3, 4 is still an allowed starting location. Additionally, location 1 becomes an allowed starting location. Indeed, if the organizers decided to change the direction of the road connecting locations 1 and 3, from location 1 one could trace a race route ending at location 1.

In the case of building an additional road from location 4 to location 5, the layout would look as follows:

In this case, each of the locations 2, 3, 4 is still an allowed starting location. Additionally, location 5 becomes an allowed starting location. It suffices to change the direction of one of the roads connecting locations 4 and 5.

Finally, in the case of building an additional road from location 5 to location 1, each of the locations would be an allowed starting location. In this case, it is not necessary to change the direction of any road.

Subtasks