You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

注意：本题输入量较大，请采用效率较高的读入方式。

注意：本题强制在线。

小 $H$ 正在和朋友游玩一款染色游戏。游戏的地图为一张有向无环图，初始所有点均没有上色。现给定两种操作：

$\texttt{1 x c}$ ：一位玩家从 $x$ 点出发，选择一条经过的点最多的简单路径（如果存在多个符合要求的路径，则选择字典序最小的路径），并把路径上的所有点涂成颜色 $c$ 。随后，查询当前图上存在的颜色总种类数（不包括无色）。

$\texttt{2 d}$ ：查询当前图上颜色为 $d$ 的点的总数量。

操作会以某种形式进行加密，详见【输入格式】部分。

给定游戏地图和操作序列，请根据操作的要求输出相应答案。

输入格式

第一行输入三个整数 $n,m,q\,(2\leq n\leq 10^6 ,\,1\leq m\leq \min(2\times10^6,\frac{n(n-1)}{2}),\,1\leq q\leq 10^6)$ ，表示图的点数、边数以及操作数。

接下来 $m$ 行，每行输入两个整数 $x,y\,(1\leq x,y\leq n)$ ，描述图上的一条有向边 $(x,y)$ .

接下来 $q$ 行，每行输入三个整数 $1, x', c'$ 或两个整数 $2, d'$ ，表示被加密后的操作信息。

操作信息的解密方法：真实的 $x,c,d$ 值分别为 $x' \oplus lastans, c' \oplus lastans, d'\oplus lastans$，其中 $lastans$ 为上一次操作的输出，$\oplus$ 为按位异或。在第一次操作时 $lastans = 0$ .

真实的值保证 $1\leq x\leq n,1\leq c,d\leq 10^6$ .

数据保证生成的有向无环图不存在重边。

输出格式

对于每一次操作，输出一行一个整数，表示该次操作的答案。

输入输出样例 #1

输入 #1

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

输出 #1

1
1
0
7

说明/提示

本题对于空间限制有相对严格的要求，请务必小心可能存在的空间限制溢出问题。