Problem M
Ab Initio

“A journey of a thousand miles begins with a single step.” ­–Lao Tzu.

When someone is studying competitive programming from the beginning, he or she is said to be a student of competitive programming ab initio. Students should be given relatively easy problems to begin their journeys, before they are gradually given more difficult problems.

Here is an example of an easy problem that does not even need a description.

Input

The first line of input contains three integers $V$ ($2 \leq V \leq 2\, 000$), $E$ ($1 \leq E \leq 200\, 000$), and $Q$ ($1 \leq Q \leq 2\, 000$), the number of vertices, the number of edges and the number of queries that must be performed on a directed, unweighted graph $G$, respectively. For simplicity, we label the vertices $0, 1, 2, \dots , V-1$.

The next $E$ lines describe the edges of $G$, given in the format of an edge list. In particular, the $i^\text {th}$ of these lines contains two integers $A_ i$ and $B_ i$ ($0\leq A_ i, B_ i < V$; $A_ i \neq B_ i$), denoting that the $i^\text {th}$ edge connects vertex $A_ i$ to vertex $B_ i$. It is guaranteed that for any pair of vertices $(a, b)$, there is at most one edge from $a$ to $b$.

The next $Q$ lines contain the queries. In particular, the $i^\text {th}$ of these lines begins with a single integer:

• If this integer is $1$, no integers follow.

  You should add a new vertex labeled $V$ to $G$. This vertex should not have edges to or from any other vertex. $V$ – the current size of $G$ – now increases by 1.

• If this integer is $2$, two integers $X_ i$ and $Y_ i$ ($0\leq X_ i, Y_ i < V$; $X_ i \neq Y_ i$) follow.

  You should add a new directed edge connecting vertex $X_ i$ to vertex $Y_ i$ in $G$. It is guaranteed that this edge does not currently exist.

• If this integer is $3$, a single integer $X_ i$ ($0\leq X_ i < V$) follows.

  You should delete all the incoming and outgoing edges of $X_ i$ from the graph $G$.

• If this integer is $4$, two integers $X_ i$ and $Y_ i$ ($0\leq X_ i, Y_ i < V$; $X_ i \neq Y_ i$) follow.

  You should remove the directed edge connecting vertex $X_ i$ to vertex $Y_ i$ from $G$. It is guaranteed that this edge currently exists.

• If this integer is $5$, no integers follow.

  You should replace $G$ with its transpose $G’$, defined as follows:
  For every pair of vertices $(a, b)$, the edge from $a$ to $b$ exists in $G’$ if and only $a \neq b$ and the edge from $b$ to $a$ exists in $G$.

• If this integer is $6$, no integers follow.

  You should replace $G$ with its complement $\bar{G}$, defined as follows:
  For every pair of vertices $(a, b)$, the edge from $a$ to $b$ exists in $\bar{G}$ if and only $a \neq b$ and the edge from $a$ to $b$ does not exist in $G$.

Output

After performing all the queries, you will have a final graph $G$. Since this graph can be very large, we will not ask you to output the entire graph. Instead, by doing the below, you can convince us that you indeed have the required graph.

1. On the first line, output a single integer $V$, the number of vertices in the graph $G$.

2. For each of the next $V$ lines, output two integers. In particular, in the $i^\text {th}$ of these lines, output:

   • $d_ i$, the outdegree of vertex $i$, and

   • $h_ i$, the hash of the adjacency list of vertex $i$, defined as follows. Suppose the vertices in the out-neighborhood of vertex $i$ are $n_1 < n_2 < \dots < n_{d_ i}$. Then

     \begin{equation*} h_ i = 7^0\cdot n_1 + 7^1\cdot n_2 + 7^2\cdot n_3 + \dots + 7^{d_ i-1}\cdot n_{d_ i} \end{equation*}

     Since $h_ i$ can be quite large, you should output only the remainder after dividing this number by $10^9+7$.

3 2 8
0 1
0 2
2 1 2
1
2 3 0
4 0 2
3 0
2 0 3
6
5

4
3 162
3 161
2 21
2 15