From Bucharest 2 Piatra Neamț

Matei, an esteemed student from the National High School of Computer Science in Piatra Neamț, is now studying in Bucharest. Hearing that the IIOT finals will take place in his hometown, he wants to make sure he doesn't miss out on the event!

The road network of Moldova and Muntenia can be modeled as a directed graph with $N$ vertices (cities) and $M$ edges (roads). The road network is in severe disrepair, so the government recently approved the construction of several new roads. The roads will be constructed in the following ways:

• $\text{1 x l r}$ — Constructs a new road from city $x$ to every city in the interval $[l, r]$.
• $\text{2 x l r}$ — Constructs a new road from every city in the interval $[l, r]$ to city $x$.
• $\text{3 l r}$ — Constructs a new road between every pair of cities $(x, y)$ within the interval $[l, r]$.

Task

Seeing the new road network, Matei wonders about the following question: how many pairs of cities $(u, v)$ are there such that both paths from $u \to v$ and $v \to u$ exist?

Input data

The first line of the input contains two space-separated integers, $N$ and $M$, where $N$ represents the number of cities in the network and $M$ the number of initial roads.

The following $M$ lines each contain two space-separated integers, $u$ and $v$, representing a road from city $u$ to city $v$ in the original network.

The following line contains the integer $Q$, the number of new construction phases.

The next $Q$ lines describe the construction phases. Each line begins with an integer $type \in \{1, 2, 3\}$, followed by additional space-separated integers corresponding to the parameters of the construction type described above.

Output data

The first line of the output must contain a single integer representing the total number of pairs $(u, v)$ for which both directed paths $u \to v$ and $v \to u$ exist in the final network.

Constraints and clarifications

• $1 \leq N, M, Q \leq 200 \ 000$
• $1 \leq u, v \leq N$ for every road in the network.
• $1 \leq x \leq N, \ 1 \leq l \leq r \leq N$ for every construction phase.

Example

stdin

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

stdout

25