Bus Routes: Minimum Transfers

You are given a network of bus routes and bus stops. Each bus route is represented as a sequence of stops, starting with an integer k that denotes the number of stops in that route, followed by k integers indicating the bus stops.

You are also given several queries. Each query consists of two integers, a starting stop u and a destination stop v. Your task is to determine the minimum number of buses required to travel from stop u to stop v. If it is not possible to travel between these stops using the given bus routes, output -1. Note that if the starting stop is the same as the destination stop, the answer is 0.

The problem can be formally defined as follows:

Given bus stops \(1, 2, \ldots, n\), m bus routes (each route is provided as \(k, s_1, s_2, \ldots, s_k\)), and q queries \((u, v)\), compute the minimum number of bus transfers (i.e. the minimum number of buses to take) required to go from \(u\) to \(v\). If no route exists, output \(-1\).

inputFormat

The first line contains three integers n, m, and q where:

• n is the number of bus stops.
• m is the number of bus routes.
• q is the number of queries.

The next m lines describe each bus route. Each route starts with an integer k (the number of stops on that route) followed by k integers representing the bus stops.

The next q lines each contain two integers u and v, representing a query to determine the minimum number of buses needed to travel from stop u to stop v.

outputFormat

For each query, output a single integer on a new line representing the minimum number of buses required to travel from the start to the destination. If it is impossible to reach the destination, output -1.

## sample

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

2
1

</p>