F. The Meeting Place Cannot Be Changed

Codeforces

IDCF982F

Time1000ms

Memory256MB

Difficulty—

dfs and similargraphs

English · Original

Chinese · Translation

Formal · Original

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping. Petr knows that it is the robbers who drive the car. The roads in Braginsk are one-directional and each of them connects two intersections. Petr wants to select one intersection such that if the robbers continue to drive the roads indefinitely, they will sooner or later come to that intersection. The initial position of the robbers is unknown. Find such an intersection that fits the requirements. ## Input The first line of the input contains two integers $n$ and $m$ ($2 \leq n \le 10^5$, $2 \leq m \leq 5 \cdot 10^5$) — the number of intersections and the number of directed roads in Braginsk, respectively. Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) — the start and finish of the $i$\-th directed road. It is guaranteed that the robbers can move along the roads indefinitely. ## Output Print a single integer $k$ — the intersection Petr needs to choose. If there are multiple answers, print any. If there are no such intersections, print $-1$. [samples] ## Note In the first example the robbers can move, for example, along the following routes: $(1-2-3-1)$, $(3-4-5-3)$, $(1-2-3-4-5-3-1)$. We can show that if Petr chooses the $3$\-rd intersection, he will eventually meet the robbers independently of their route.

Petr 是 Braginsk 的一名侦探。有人从银行偷走了一大笔钱，Petr 要抓住他。有人告诉 Petr，一辆豪华汽车正在道路上不停歇地行驶。 Petr 知道，这辆车正是劫匪驾驶的。Braginsk 的道路都是单向的，每条道路连接两个交叉口。Petr 希望选择一个交叉口，使得无论劫匪如何持续在道路上行驶，他们迟早都会到达这个交叉口。劫匪的初始位置未知。请找出一个满足要求的交叉口。输入的第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 10^5$，$2 lt.eq m lt.eq 5 dot.op 10^5$）—— 分别表示交叉口的数量和 Braginsk 中有向道路的数量。接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 lt.eq u_i, v_i lt.eq n$，$u_i != v_i$）—— 表示第 $i$ 条有向道路的起点和终点。保证劫匪可以无限期地在道路上行驶。请输出一个整数 $k$ —— Petr 需要选择的交叉口。如果有多个答案，输出任意一个即可。如果没有这样的交叉口，请输出 $-1$。在第一个例子中，劫匪可以沿以下路径之一移动：$(1 -2 -3 -1)$，$(3 -4 -5 -3)$，$(1 -2 -3 -4 -5 -3 -1)$。我们可以证明，如果 Petr 选择第 $3$ 个交叉口，无论劫匪选择哪条路径，他最终都会与劫匪相遇。 ## Input 输入的第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 10^5$，$2 lt.eq m lt.eq 5 dot.op 10^5$）—— 分别表示交叉口的数量和 Braginsk 中有向道路的数量。接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 lt.eq u_i, v_i lt.eq n$，$u_i != v_i$）—— 表示第 $i$ 条有向道路的起点和终点。保证劫匪可以无限期地在道路上行驶。 ## Output 请输出一个整数 $k$ —— Petr 需要选择的交叉口。如果有多个答案，输出任意一个即可。如果没有这样的交叉口，请输出 $-1$。 [samples] ## Note 在第一个例子中，劫匪可以沿以下路径之一移动：$(1 -2 -3 -1)$，$(3 -4 -5 -3)$，$(1 -2 -3 -4 -5 -3 -1)$。我们可以证明，如果 Petr 选择第 $3$ 个交叉口，无论劫匪选择哪条路径，他最终都会与劫匪相遇。

**Definitions** Let $ G = (V, E) $ be a directed graph with: - $ V = \{1, 2, \dots, n\} $: set of vertices (intersections), - $ E \subseteq V \times V $: set of directed edges (roads), $ |E| = m $. **Constraints** 1. $ 2 \le n \le 10^5 $ 2. $ 2 \le m \le 5 \cdot 10^5 $ 3. No self-loops: $ \forall (u,v) \in E, u \ne v $ 4. The graph is such that every infinite walk eventually enters a cycle (robbers move indefinitely). **Objective** Find a vertex $ k \in V $ such that **every** infinite walk on $ G $ (starting from any vertex) will eventually visit $ k $. Equivalently: Find a vertex $ k $ that lies in **every** strongly connected component (SCC) that is a sink (i.e., has no outgoing edges to other SCCs), and such that **all** cycles in the graph are contained within a single such sink SCC, and $ k $ is in that SCC. If multiple such $ k $ exist, output any. If no such vertex exists, output $-1$. **Note**: The desired vertex $ k $ must belong to the **unique** sink SCC (if it exists) that is reachable from all other vertices. If there is more than one sink SCC, then no such $ k $ exists.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. The Meeting Place Cannot Be Changed",
    "description": {
      "content": "Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping. Petr kn",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF982F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping.\n\nPetr kn...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petr 是 Braginsk 的一名侦探。有人从银行偷走了一大笔钱，Petr 要抓住他。有人告诉 Petr，一辆豪华汽车正在道路上不停歇地行驶。\n\nPetr 知道，这辆车正是劫匪驾驶的。Braginsk 的道路都是单向的，每条道路连接两个交叉口。Petr 希望选择一个交叉口，使得无论劫匪如何持续在道路上行驶，他们迟早都会到达这个交叉口。劫匪的初始位置未知。请找出一个满足要求的交叉口。\n\n输入的第...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $: set of vertices (intersections),  \n- $ E \\subseteq V \\times V $: set of directed edges (roads), $ |E| = m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments