圣芙蕾雅

Problem Description

为了对抗崩坏，圣芙蕾雅学院培养了 $k$ 位女武神（从 $1$ 到 $k$ 编号），这些女武神参加了一系列战斗。现共有 $n$ 次事件记录（从 $1$ 到 $n$ 编号），共有两种类型的记录，第 $1$ 种为装甲分配记录，包含 $1$ 位女武神的编号，表示分配给该女武神 $1$ 套装甲；第 $2$ 种为战斗记录，包含 $1$ 位女武神的编号，表示该女武神参加了这次战斗。受到崩坏的影响，事件记录的先后顺序发生了错乱，只能确保 $1$ 号事件是最早发生的，同时有 $m$ 条可能的先后关系。 简单来说，可以把 $n$ 次事件看成 $n$ 个点，$m$ 条先后关系看成 $m$ 条有向边；$1$ 条由 $x$ 连向 $y$ 的有向边表示 $x$ 事件的下一次事件可能是 $y$，没有边连向 $1$ 号点。注意，图可能有环，即同一事件可能多次发生。 装甲归还的记录已经丢失，现已知每位女武神至多只会被分配 $1$ 次装甲，且每次参加战斗时，必须已经被分配装甲且未归还。一套装甲在分配给一位女武神且未归还的情况下不能分配给其他女武神，但是在归还后可以分配给其他女武神。现在希望你尝试还原装甲归还记录，但是由于信息不足，无法真正还原，因此你只需要计算圣芙蕾雅学院至少拥有多少套装甲，才有可能满足所有要求。你可以将装甲归还事件添加在任意事件的前后，且添加次数不限，只要保证在每个战斗事件时，该女武神一定已分配装甲且未归还即可。

Input

第一行输入一个正整数 $t\ (1\le t\le 5)$ 代表数据组数。 对于每组数据： 第一行 $3$ 个正整数 $n,m,k\ (1\leq n,k\leq 3\times 10^3,1\leq m\leq 10^4)$，分别表示事件的数量，可能的先后关系的数量和女武神的数量。 接下来共 $n$ 行，其中第 $i$ 行 $2$ 个正整数 $opt_i,x_i(opt_i\in$ { $1,2$ } $,1\leq x_i\leq k)$：

• 如果 $opt_i=1$ 则表示事件为给 $x_i$ 女武神分配 $1$ 套装甲。
• 如果 $opt_i=2$ 则表示 $x_i$ 女武神参加了战斗。 接下来共 $m$ 行，其中第 $i$ 行 $2$ 个正整数 $u,v(1\leq u,v \leq n,u\neq v)$ 表示 $u$ 事件的下一事件可能是 $v$ 事件。 数据保证任意事件都有可能发生，保证不会出现战斗事件发生时，参战女武神还未被分配装甲。

Output

对每组数据输出 $1$ 行 $1$ 个整数，表示圣芙蕾雅学园至少拥有的装甲数量。

Sample Input

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

Sample Output

2

Source

2024“钉耙编程”中国大学生算法设计超级联赛（3）