Problem D
Box and Arrow Diagram

An example of a box and arrow diagram, taken from github.com/dicander/box_arrow_diagram

In this part of the exam you are given a piece of Python code and you have to draw how the memory structure will look like when the program reaches a given line. Since Itaf is a high-rated competitive programmer her ego always came in the way whenever she tried to study for the test, because it felt “too easy”. But now she has become desperate and needs your help.

The box and arrow diagram is used to explain the memory structure inside Python. Simplified, the diagram can be seen as a directed graph with nodes (boxes) labeled from $1$ to $N$ and edges (arrows) labeled from $1$ to $M$. The boxes corresponds to the objects in the memory of a Python program. Box 1 is special, it represents the global object. An arrow being drawn from box $u$ to box $v$ in the diagram means that object $u$ stores a reference of object $v$. If $u$ stores multiple references of $v$, then you draw multiple arrows from $u$ to $v$. It is also possible for an object to contain references to itself.

An object $u$ is said to be alive if there exists a path from the global object to $u$ in the box and arrow diagram. Each object also has a reference counter. The reference counter of an object $u$ is defined as the number of arrows $(v,u)$ such that $v$ is alive.

Itaf now needs your help, and she will ask you $Q$ queries, each query can be one of two types.

• 1 X   Output the reference counter of the object with label $X$.

• 2 Y   Remove the arrow with label $Y$ from the diagram.

Input

The first line consists of two space separated integers $N,M$ ($1 \leq N,M \leq 2 \cdot 10^5$), where $N$ is the number of boxes in the diagram and $M$ is the number of arrows in the diagram.

The next $M$ lines describe the arrows in the diagram. The $i$-th line contains $2$ space separated integers $U_ i,V_ i$ ($1 \leq U_ i,V_ i \leq N$), meaning the arrow with label $i$ goes from box $U_ i$ to box $V_ i$. Note that arrows forming loops and multi-edges are allowed.

The next line contains an integer $Q$ ($1 \leq Q \leq 2 \cdot 10^5$), the number of queries. The next $Q$ lines describe the $Q$ queries. The $j$-th query is given as a pair of space separated integers $C_ j, X_ j$ ($1 \leq C_ j \leq 2$).

• If $C_ j = 1$ then remove the arrow labeled $X_ j$ from the diagram ($1 \leq X_ j \leq M$).

• If $C_ j = 2$ then output the reference counter of object $X_ j$ ($1 \leq X_ j \leq N$).

It is guaranteed that there will not be two queries of type $1$ with same value of $X_ j$, meaning the same arrow will never be deleted twice.

Output

For each query of type $2$, output a single line containing the reference count of object $Y_ j$.

3 4
1 2
2 3
1 2
3 3
7
2 2
2 3
1 4
2 3
1 1
1 3
2 3

2
2
1
0