25271번 - Box and Arrow Diagram 다국어

문제

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

What an embarrassment! Itaf got 0/5 points in her last "Fundamental programming in Python" exam. She studies Engineering physics at KTH and is struggling with this course. She is not alone, as 60ドル\%$ of her classmates failed the exam this year. The reason for this oddly high percentage is the so called box and arrow diagram (låd- och pildiagram).

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 Remove the arrow with label $X$ from the diagram.}
• 2 Y Output the reference counter of the object with label $Y$.}

입력

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.

출력

For each query of type 2ドル,ドル output a single line containing the reference count of object $Y_j$.

제한

힌트