题目描述

Ivo 住在保加利亚，而且非常喜欢坐飞机。只有在前往机场赶航班时，他才会乘坐公交车。他是如此热爱飞行，以至于开始思考：自己最多能连续赶上多少个航班。

保加利亚有 N 个城市，编号为 0 到 N-1，并有 M 条不同的双向公交线路。每条线路连接两个不同的城市，并且每天都有双向班车运行。接下来的 T 天中，每天恰好有一班航班。第 i 天的航班从城市 c_i 飞往城市 d_i。

在整个旅程开始时，Ivo 处在某个他可以自由选择的城市 g_0。之后他的行动规则如下：若在第 i 天开始时他位于城市 g_i，那么他可以执行以下三种操作之一：

1. 一直待在当前城市直到下一天，也就是 g_{i+1} = g_i。
2. 从当前所在城市直接乘坐当天的航班，也就是 g_i = c_i 且 g_{i+1} = d_i。
3. 先从当前所在城市乘一班公交到另一个城市，再从那里搭乘当天的航班，也就是 (g_i, c_i) 是一条公交线路，且 g_{i+1} = d_i。

遗憾的是，Ivo 对计算机不太擅长，不知道如何找出最优路线，使得他在接下来的 T 天中能赶上的航班数量最大。因此他来向你求助。请编写程序 flights，求出 Ivo 最多能赶上多少个航班。

输入格式

第一行输入三个整数 N、M 和 T，分别表示城市数、公交线路数和天数。

接下来 N 行描述各城市的公交线路。对城市 j 所在的那一行，先输入一个整数 k_j，表示经过城市 j 的公交线路数量；随后输入 k_j 个整数，表示与城市 j 直接有公交线路连接的其他城市编号。

注意，这意味着每条线路 (a, b) 会在输入中出现两次：一次在城市 a 的那一行，一次在城市 b 的那一行。

接下来 T 行，每行输入两个整数 c_i 和 d_i，表示第 i 天航班的起点城市和终点城市。

输出格式

输出一个整数，表示 Ivo 最多能赶上的航班数。

约束

• 1 ≤ N ≤ 5 × 10^5
• 1 ≤ M ≤ 10^6
• 1 ≤ T ≤ 5 × 10^5

子任务

子任务的分数只有在该子任务下的所有测试点全部通过时才能获得。

样例

输入

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

输出

4

说明

一开始，Ivo 选择从城市 0 出发。

• 第一天，他直接搭乘 0 -> 4 的航班。
• 第二天，他待在城市 4 不动。
• 第三天，他搭乘航班 2 -> 1，因为有一条公交线路可以把他从 4 送到 2。
• 第四天，他直接搭乘 1 -> 3 的航班。
• 第五天，他搭乘航班 0 -> 5，因为有一条公交线路可以把他从 3 送到 0。

因此，他一共赶上了 4 个航班。