ACAC 题库 ac.isam.top
GitHub
SMBC 编程竞赛 #2（第 481 场 AtCoder Beginner Contest）
D
自动驾驶
Autopilot
AtCoder
⌀ 581
原题
← CE →

自动驾驶AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

There are $N$ planets and $M$ routes. The planets are numbered $1$ to $N$, and the routes are numbered $1$ to $M$.

有 $N$ 个行星和 $M$ 条航线。行星编号为 $1$ 到 $N$，航线编号为 $1$ 到 $M$。AI (CI翻译)

Route $i$ goes from planet $A_i$ to planet $B_i$. Each route is one-way.

航线 $i$ 从行星 $A_i$ 通往行星 $B_i$。每条航线都是单向的。AI (CI翻译)

A spaceship can perform the following two types of operations.

宇宙飞船可以执行以下两种操作。AI (CI翻译)

  • Move, without consuming fuel, to the planet with the smallest number among the planets directly reachable by a route from the current planet.
  • Choose any planet directly reachable by a route from the current planet, and move to the chosen planet, consuming $1$ unit of fuel.
  • 不消耗燃料，移动到从当前行星出发、通过一条航线可以直接到达的行星中编号最小的行星。
  • 从通过一条航线可以直接到达的行星中任选一个，移动到该行星，并消耗 $1$ 单位燃料。
AI (CI翻译)

Find the minimum amount of fuel the spaceship consumes to start from planet $S$ and arrive at planet $T$. If it is impossible to reach planet $T$, print $-1$ instead.

求宇宙飞船从行星 $S$ 出发并到达行星 $T$ 所消耗的最少燃料。如果无法到达行星 $T$，则输出 $-1$。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $1 \leq S,T \leq N$
  • $S \neq T$
  • $1 \leq A_i, B_i \leq N$
  • $A_i \neq B_i$
  • All input values are integers.
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $1 \leq S,T \leq N$
  • $S \neq T$
  • $1 \leq A_i, B_i \leq N$
  • $A_i \neq B_i$
  • 所有输入值均为整数。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N M S T
A_1 B_1
\vdots
A_M B_M

N M S T
A_1 B_1
\vdots
A_M B_M
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Print the answer.

输出答案。AI (CI翻译)

样例

Input #1
7 10 2 1
2 5
2 4
4 2
4 3
3 1
3 5
3 6
5 6
6 1
6 7
Output #1
1
By moving in the following order, the spaceship can travel from planet $2$ to planet $1$ with a fuel consumption of $1$. 1. Move from planet $2$ to planet $4$ without consuming fuel. 2. Move from planet $4$ to planet $3$, consuming $1$ unit of fuel. 3. Move from planet $3$ to planet $1$ without consuming fuel.
Input #2
7 10 2 7
2 5
2 4
4 2
4 3
3 1
3 5
3 6
5 6
6 1
6 7
Output #2
2
By moving in the following order, the spaceship can travel from planet $2$ to planet $7$ with a fuel consumption of $2$. 1. Move from planet $2$ to planet $4$ without consuming fuel. 2. Move from planet $4$ to planet $2$ without consuming fuel. 3. Move from planet $2$ to planet $5$, consuming $1$ unit of fuel. 4. Move from planet $5$ to planet $6$ without consuming fuel. 5. Move from planet $6$ to planet $7$, consuming $1$ unit of fuel.
Input #3
2 1 1 2
2 1
Output #3
-1
It is impossible to start from planet $1$ and reach planet $2$.
题目信息
题号
abc481_d
所属比赛
SMBC 编程竞赛 #2（第 481 场 AtCoder Beginner Contest）
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。