Brothers in Arms

In medieval times, keeping track of relationships between cities was extremely difficult, since most cities did not have access to the internet[citation needed]. However, it was possible to determine whether two cities were friendly by examining their coats of arms. Every coat of arms showed two symbols: one at the top and one at the bottom. If two cities have an equal symbol at the top, or an equal symbol at the bottom, they are friendly.

Following the saying "the friends of my friends are my friends", two cities $c\_0$ and $c\_f$ are indirectly friendly if there exist cities $c\_1, \ldots, c\_{f-1}$ such that $c\_k$ is friendly with $c\_{k+1}$ for $0\leq k < f$. If $c\_0$ and $c\_f$ are different and indirectly friendly, then the friendship degree of these cities is the smallest possible $f$ following this definition. See Figure B.1 for an example.

Parts of these coats of arms are CC BY-SA 4.0 on Wikimedia Commons.

Figure B.1: Illustration of Sample Input 1. Cities 1 and 2 are directly friendly, as are cities 2 and 3. Cities 1 and 3 have a friendship degree of 2, because they are indirectly friendly via city 2. City 4 is not (indirectly) friendly with any other city.

You are given a list of coats of arms and a list of queries. For every query, determine the friendship degree of the two given cities.

The input consists of:

One line with two integers $n$ and $s$ ($2\leq n\leq 90\,000$, $2\leq s\leq 300$), the number of cities and the number of symbols that may appear on the coat of arms of some city.

$n$ lines, the $i$th of which consists of two integers $t_i$ and $b_i$ ($1\leq t_i, b_i\leq s$). $t_i$ is the symbol on the top side of the coat of arms of the $i$th city, and $b_i$ is the symbol on the bottom side. If $i\neq j$, then $t_i\neq t_j$ or $b_i\neq b_j$.

One line with an integer $q$ ($1\leq q\leq 10^5$), the number of queries.

$q$ lines, the $i$th of which contains two integers $c$ and $d$ ($1\leq c, d\leq n$, $c\neq d$), two cities for which you should calculate the friendship degree.

For every query, output an integer stating the friendship degree of the two cities, or $-1$ if the two cities are not (indirectly) friendly.