I. Interlingual Intermediaries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Over the ages, each people developed its own way of speaking, and each language carried the culture and way of life of its speakers. The Elves created Elvish, a softer and more elegant language; the dragons created Draconic, representing their dominance and ferocity; and, little by little, all the other peoples created their own languages as they pleased.

A great meeting among diplomats from $$$N$$$ peoples will be held to discuss the future of the continent. The event has a total of $$$M$$$ cataloged languages. The problem is that not all diplomats share a common language. For a message to get from one point to another, it may be necessary to use other diplomats as intermediaries.

However, every time the message must be translated from one language to another (when an intermediary hears it in one language and speaks it in another), a language switch occurs. To minimize misunderstandings, the conclave organizers need to find the minimum number of switches required for two diplomats to communicate.

Given the sets of languages spoken by each of the $$$N$$$ diplomats and $$$Q$$$ queries $$$(a, b)$$$, determine the minimum number of language switches needed for diplomats $$$a$$$ and $$$b$$$ to communicate. If communication is impossible, print $$$-1$$$.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$2 \leq N \leq 10^{4}, 1 \leq M \leq 30, 1 \leq Q \leq 2 \times 10^{5}$$$), the number of diplomats, the total number of languages, and the number of queries, respectively.

Then $$$N$$$ lines follow, each composed first of an integer $$$m_i$$$ $$$(1 \le m_i \le M)$$$ – how many languages the $$$i$$$-th diplomat speaks – followed by $$$m_i$$$ distinct values $$$\ell_1, \ldots, \ell_{m_i}$$$ ($$$1 \leq \ell \leq M$$$) – the languages spoken by the diplomat.

Finally, the input contains $$$Q$$$ more lines, each containing two integers $$$a$$$ and $$$b$$$ $$$(1 \leq a, b \leq N, a \ne b)$$$, the initial and final diplomats in the query.

Output

The output should contain $$$Q$$$ lines, each answering how many language switches are necessary for $$$a$$$ and $$$b$$$ to communicate; if it is not possible, print $$$-1$$$.

Example
Input
6 7 3
2 3 6
3 3 2 7
2 1 2
2 1 5
1 4
1 1
4 1
2 3
2 5
Output
2
0
-1
Note

Explanation for example 1

  • In the first query, one possible way to transmit the message is:

    $$$4 \xrightarrow{\text{language $$$1$$$}} 6 \xrightarrow{\text{language $$$1$$$}} 3 \xrightarrow{\text{language $$$2$$$}} 2 \xrightarrow{\text{language $$$3$$$}} 1$$$ – with two language switches, $$$1/2$$$ and $$$2/3$$$.

  • In the second query, the message can be transmitted with no language switches: $$$2 \xrightarrow{\text{language $$$2$$$}} 3$$$.

  • In the third query, diplomat $$$5$$$ speaks only language number $$$4$$$, which is not spoken by anyone else, so it is not possible to transmit the message to them.