题目描述

马泰是一名来自皮亚特拉-尼亚姆茨国立信息学高中的优秀学生，目前正在布加勒斯特学习。听说 IIOT 总决赛将在家乡举办后，他希望确保自己不会错过比赛。

摩尔达维亚和蒙特尼亚的道路网络可以表示为一张包含 $N$ 个顶点（城市）和 $M$ 条有向边（道路）的有向图。

由于道路年久失修，政府批准了若干轮新道路建设。每轮建设属于以下三种类型之一：

1. 1 x l r：从城市 $x$ 向区间 $[l,r]$ 中的每一座城市修建一条有向道路；
2. 2 x l r：从区间 $[l,r]$ 中的每一座城市向城市 $x$ 修建一条有向道路；
3. 3 l r：对于区间 $[l,r]$ 中的任意一对城市 $(x,y)$，修建从 $x$ 到 $y$ 的道路。换言之，该区间内任意两座城市之间都可以直接双向到达。

在所有道路建设完成后，马泰想知道：有多少个有序城市对 $(u,v)$，满足既存在从 $u$ 到 $v$ 的路径，也存在从 $v$ 到 $u$ 的路径？

允许 $u=v$。

输入格式

第一行包含两个整数 $N,M$，分别表示城市数量和初始道路数量。

接下来 $M$ 行，每行包含两个整数 $u,v$，表示初始道路网络中存在一条从 $u$ 指向 $v$ 的道路。

下一行包含一个整数 $Q$，表示道路建设轮数。

接下来 $Q$ 行描述各轮建设。每行首先给出一个整数 type：

• 1 x l r；
• 2 x l r；
• 3 l r。

其含义见题目描述。

输出格式

输出一个整数，表示最终网络中满足 $u\to v$ 和 $v\to u$ 均可达的有序城市对 $(u,v)$ 的数量。

数据范围

• $1\le N,M,Q\le 200000$；
• $1\le u,v\le N$；
• 对每轮建设，$1\le x\le N$，$1\le l\le r\le N$。

子任务

样例

输入

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

输出

25