[ICPC2022 Xi'an R] Contests
题意翻译
### 题目描述
$n$ 个选手参加了 $m$ 场比赛。给出每场比赛的排行榜。第 $k$ 场比赛的排行榜是一个 $n$ 阶排列 $a_k$,表示选手 $a_{k, i}$ 的排名为 $i$。
SolarPea 和 PolarSea 也是选手。SolarPea 想要证明他比 PolarSea 更强。
定义选手 $x$「$l$ - 强于」选手 $y$,当且仅当存在长度为 $l + 1$ 的序列,满足 $b_1 = x$,$b_{l + 1} = y$,且对于所有 $1\leq i\leq l$,均有 $b_i$ 在至少一场比赛中排名小于 $b_{i + 1}$。
给出 $q$ 组询问。在第 $i$ 组询问中,SolarPea 是选手 $x$,PolarSea 是选手 $y$。求出最小的正整数 $l$,使得 $x$「$l$ - 强于」$y$。
$2\leq n\leq 10 ^ 5$,$1\leq q\leq 10 ^ 5$,$1\leq m\leq 5$,$1\leq x, y\leq n$,$x\neq y$。
### 输入格式
第一行两个整数 $n, m$。
接下来 $m$ 行,每行 $n$ 个整数,表示第 $i$ 场比赛的排行榜。保证 $a_i$ 是 $1, 2, \ldots, n$ 的排列。
接下来一行一个整数 $q$。
接下来 $q$ 行,每行两个整数 $x, y$ 表示一组询问。
### 输出格式
对于每组询问,输出一行一个整数表示答案。若不存在这样的 $l$,输出 $-1$。
题目描述
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 l$, $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$.
输入输出样例
输入样例 #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
1
2
5
3
说明
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem D.
**Author**: csy2005.