[BalticOI 2022] Event Hopping (Day1)

Luogu

IDLGP8391

Time1000ms

Memory128MB

DifficultyP6

2022BalticOI（波罗的海）

有 $n$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$。你可以在区间之间跳跃。当你在第 $x$ 个区间上时，你可以跳到一个覆盖右端点 $r_x$ 的区间 $y$ 上，即从 $x$ 能跳到 $y$ 当且仅当 $[r_x \in [l_y,r_y]]$。有 $q$ 次询问，每次你一开始在第 $s_i$ 个区间，你需要跳到第 $t_i$ 个区间。你需要输出你至少需要跳多少次。如果不能跳到，输出 `impossible`。 ## Input 第一行，两个整数 $n, q$。接下来 $n$ 行，每行两个整数 $l_i$，$r_i$。接下来 $q$ 行，每行两个整数 $s_i$，$t_i$。 ## Output 输出 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案。如果无解输出 `impossible`。 [samples] ## Note - 子任务 $1$ ($10$ 分)：每一个区间可以跳到至多一个其他区间。 - 子任务 $2$ ($10$ 分)：$n≤ 1000$，$q ≤100$。 - 子任务 $3$ ($15$ 分)：$n≤5000$。 - 子任务 $4$ ($15$ 分)：$q ≤100$。 - 子任务 $5$ ($20$ 分)：不存在两个区间 $i,j$ 满足 $[l_i, r_i] \subseteq [l_j,r_j]$。 - 子任务 $6$ ($30$ 分)：没有特殊限制。对于所有数据，满足 $1≤n,q ≤100000$，$1≤l_i<r_i≤10^9$，$1≤s_i,t_i≤n$。

Samples

Input #1

Output #1

2
impossible

Input #2

8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

Output #2

3
4
impossible
0
impossible

API Response (JSON)

{
  "problem": {
    "name": "[BalticOI 2022] Event Hopping (Day1)",
    "description": {
      "content": "有 $n$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$。 你可以在区间之间跳跃。当你在第 $x$ 个区间上时，你可以跳到一个覆盖右端点 $r_x$ 的区间 $y$ 上，即从 $x$ 能跳到 $y$ 当且仅当 $[r_x \\in [l_y,r_y]]$。 有 $q$ 次询问，每次你一开始在第 $s_i$ 个区间，你需要跳到第 $t_i$ 个区间。你需要输出你至少需要跳多少次。如果不能跳",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8391"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$。\n\n你可以在区间之间跳跃。当你在第 $x$ 个区间上时，你可以跳到一个覆盖右端点 $r_x$ 的区间 $y$ 上，即从 $x$ 能跳到 $y$ 当且仅当 $[r_x \\in [l_y,r_y]]$。\n\n有 $q$ 次询问，每次你一开始在第 $s_i$ 个区间，你需要跳到第 $t_i$ 个区间。你需要输出你至少需要跳多少次。如果不能跳...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments