410691: GYM104077 D Contests

There are $$$n$$$ contestants and they take part in $$$m$$$ contests. You are given the ranklist of each contest. The ranklist of the $$$k$$$-th contest is a sequence $$$a_k$$$, indicating that the $$$a_{k, i}$$$-th contestant's rank is $$$i$$$.

SolarPea and PolarSea are two of the $$$n$$$ contestants. SolarPea wants to prove that he is stronger than PolarSea.

Define $$$x$$$ is $$$l$$$-stronger than $$$y$$$, if and only if there exists a sequence $$$b$$$ of length $$$l + 1$$$, such that $$$b_1 = x$$$, $$$b_{l + 1} = y$$$, and for all $$$1\leq i\leq k$$$, $$$b_i$$$ has a smaller rank than $$$b_{i + 1}$$$ in at least one contest.

There are $$$q$$$ queries. In the $$$i$$$-th query, SolarPea is contestant $$$x$$$ and PolarSea is contestant $$$y$$$. Please find the minimum positive number $$$l$$$ such that SolarPea is $$$l$$$-stronger than PolarSea.

The first line contains two integers $$$n$$$ ($$$2\leq n\leq 10 ^ 5$$$) and $$$m$$$ ($$$1\leq m\leq 5$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains $$$n$$$ intergers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$. It is guaranteed that $$$a_i$$$ is a permutaion of $$$1,2,\ldots,n$$$.

The next line contains an integer $$$q$$$ ($$$1\leq q\leq 10 ^ 5$$$).

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x,y \le n, x \neq y$$$), representing a query.

For each query, output a number $$$l$$$ representing the answer. If there is no legal $$$l$$$, output $$$-1$$$.

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

1
2
5
3