{"problem":{"name":"[ICPC 2022 Xi'an R] Contests","description":{"content":"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 cont","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9361"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nSolarPea and PolarSea are two of the $n$ contestants. SolarPea wants to prove that he is stronger than PolarSea.\n\nDefine $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.\n\nThere 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.\n\n## Input\n\nThe first line contains two integers $n$ ($2\\leq n\\leq 10 ^ 5$) and $m$ ($1\\leq m\\leq 5$).\n\nThe $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$.\n\nThe next line contains an integer $q$ ($1\\leq q\\leq 10 ^ 5$).\n\nEach of the next $q$ lines contains two integers $x$ and $y$ ($1 \\le x,y \\le n, x \\neq y$), representing a query.\n\n## Output\n\nFor each query, output a number $l$ representing the answer. If there is no legal $l$, output $-1$.\n\n[samples]\n\n## Note\n\n**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem D.\n\n**Author**: csy2005.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9361","tags":["倍增","2022","O2优化","ICPC","西安"],"sample_group":[["6 2\n1 3 2 5 4 6\n2 1 4 3 6 5\n4\n1 4\n5 3\n6 1\n5 2\n","1\n2\n5\n3\n"]],"created_at":"2026-03-03 11:09:25"}}