Problem Background

The passenger flow of a city's subway system is a crucial indicator, reflecting the constantly moving population within the city. Whether for commuting or tourism, it brings vitality to the city's economy.

During the pandemic, subway passenger flows were dismal, with some cities even suspending subway operations. Now that the pandemic situation has improved, and various regions are gradually resuming work and production, the size of subway passenger flows is also an important reference for judging the city's recovery and economic recovery rate.

Problem Description

The subway system in Skyward City consists of $M$ lines, with a total of $N$ stations, each station being served by at least one line. Each line's adjacent stations can be considered connected by undirected edges. The $i$-th subway line has $k_i$ stations, all of which are distinct.

These lines intersect at some stations, meaning a station may be served by multiple lines.

Now, there are $P$ passengers who want to travel from station $s_j$ to station $t_j$, guaranteed to be different stations. When these stations are not on the same line, they will make several transfers. As a technical staff member of Skyward City's subway system, you need to calculate the passenger flow contributed by these passengers.

Note that the method of calculating passenger flow used here differs from that in practical applications.

Passenger flow = Entry flow + Transfer flow. Entry flow is the number of passengers; Transfer flow is the number of transfers made by passengers. There may be multiple paths between the start and end points, but the subway passenger flow is independent of the path chosen by the passenger; we only consider the path with the least number of transfers when calculating.

Notes:

• Suppose the minimum number of transfers from $s$ to $t$ is $\rm$, then the passenger will take $\rm trans + 1$ lines, contributing $\rm trans + 1$ to the passenger flow.
• When a passenger cannot reach the destination from the starting point, i.e., there is no path between $s$ and $t$, they will take a bus, and the passenger flow is counted as $0$.

Input Format

The first line contains three integers $N, M, P$.

The next $M$ lines describe each subway line:
- The first integer on each line is $k_i\ (2 \le k_i \le N)$, the number of stations on this line;
- The following $k_i$ integers $q\ (1 \le q \le N)$ are the station numbers this line passes through in order.

The next $P$ lines contain two integers each, $s_j, t_j\ (1 \le s_j, t_j \le N;\ s_j \neq t_j)$, indicating the starting and ending stations of a passenger's journey.

Output Format

Output a single integer, the total passenger flow contributed by these passengers.

Sample Input and Output

Input Sample #1

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

Output Sample #1

9

Input Sample #2

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

Output Sample #2

7

Input Sample #3

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

Output Sample #3

3

Notes

Sample explanations:

• Passengers always choose the path with the least number of transfers.
• Numbers on the edges indicate the subway line numbers.

For all data:

• $2 \le N \le 10^5$;
• $1 \le M \le 1000$;
• $1 \le P \le 100$;
• $1 \le \mathrm{siz}_i \le 50$.

This problem uses batched testing.

Due to the large amount of input, avoid using cin without disabling synchronization.

You can disable cin synchronization with std::ios::sync_with_stdio(false).

Alternatively, you can use the following fast input template, which supports reading non-negative integers within the int range.

int readInt() {
    int ret = 0; char o;
    while (!isdigit(o = getchar()));
    do ret = ret * 10 + (o ^ 48);
    while (isdigit(o = getchar()));
    return ret;
}

见题面 Input 部分

见题面 Output 部分