E. We Need More Bosses

Codeforces

IDCF1000E

Time2000ms

Memory256MB

Difficulty—

dfs and similargraphstrees

English · Original

Chinese · Translation

Formal · Original

Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of $n$ locations connected by $m$ **two-way** passages. The passages are designed in such a way that it should be possible to get from any location to any other location. Of course, some passages should be guarded by the monsters (if you just can go everywhere without any difficulties, then it's not fun, right?). Some crucial passages will be guarded by really fearsome monsters, requiring the hero to prepare for battle and designing his own tactics of defeating them (commonly these kinds of monsters are called **bosses**). And your friend wants you to help him place these bosses. The game will start in location $s$ and end in location $t$, but these locations are not chosen yet. After choosing these locations, your friend will place a boss in each passage such that it is impossible to get from $s$ to $t$ without using this passage. Your friend wants to place as much bosses as possible (because more challenges means more fun, right?), so he asks you to help him determine the maximum possible number of bosses, considering that any location can be chosen as $s$ or as $t$. ## Input The first line contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$, $n - 1 \le m \le 3 \cdot 10^5$) — the number of locations and passages, respectively. Then $m$ lines follow, each containing two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$) describing the endpoints of one of the passages. It is guaranteed that there is no pair of locations directly connected by two or more passages, and that any location is reachable from any other location. ## Output Print one integer — the maximum number of bosses your friend can place, considering all possible choices for $s$ and $t$. [samples]

你的朋友正在开发一款电脑游戏。他已经决定了游戏世界的结构——它由 $n$ 个地点通过 $m$ 条*双向*通道连接而成。这些通道的设计保证了从任意地点都能到达其他任意地点。当然，某些通道需要由怪物把守（如果你可以毫无困难地随意通行，那就不有趣了，对吧？）。一些关键通道将由极其可怕的怪物把守，要求英雄做好战斗准备并设计击败它们的战术（通常这类怪物被称为*首领*）。你的朋友希望你帮助他放置这些首领。游戏从地点 $s$ 开始，到地点 $t$ 结束，但这两个地点尚未确定。在选定这两个地点后，你的朋友将在每个从 $s$ 到 $t$ 必须经过的通道上放置一个首领。你的朋友希望放置尽可能多的首领（因为更多的挑战意味着更多的乐趣，对吧？），因此他请你帮他确定在所有可能的 $s$ 和 $t$ 选择下，能放置的首领的最大数量。第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 3 dot.op 10^5$，$n -1 lt.eq m lt.eq 3 dot.op 10^5$）——分别表示地点数量和通道数量。接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 lt.eq x, y lt.eq n$，$x != y$），描述一条通道的两个端点。保证不存在任意两个地点之间有两条或更多通道，且任意地点均可从其他任意地点到达。请输出一个整数——你的朋友在所有可能的 $s$ 和 $t$ 选择下能放置的首领的最大数量。 ## Input 第一行包含两个整数 $n$ 和 $m$（$2 lt.eq n lt.eq 3 dot.op 10^5$，$n -1 lt.eq m lt.eq 3 dot.op 10^5$）——分别表示地点数量和通道数量。接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 lt.eq x, y lt.eq n$，$x != y$），描述一条通道的两个端点。保证不存在任意两个地点之间有两条或更多通道，且任意地点均可从其他任意地点到达。 ## Output 请输出一个整数——你的朋友在所有可能的 $s$ 和 $t$ 选择下能放置的首领的最大数量。 [samples]

**Definitions** Let $ G = (V, E) $ be an undirected, connected graph with $ |V| = n $, $ |E| = m $, and no multiple edges. A *bridge* is an edge whose removal increases the number of connected components of $ G $. Let $ \mathcal{B} \subseteq E $ denote the set of all bridges in $ G $. For any pair of distinct vertices $ s, t \in V $, define $ B(s,t) \subseteq E $ as the set of edges that lie on *every* simple path from $ s $ to $ t $. **Constraints** 1. $ 2 \le n \le 3 \cdot 10^5 $ 2. $ n - 1 \le m \le 3 \cdot 10^5 $ 3. $ G $ is connected and simple. **Objective** Compute: $$ \max_{\substack{s, t \in V \\ s \ne t}} |B(s,t)| $$ That is, the maximum number of edges that are common to all paths between any pair of distinct vertices $ s $ and $ t $, over all possible choices of $ s $ and $ t $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. We Need More Bosses",
    "description": {
      "content": "Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of $n$ locations connected by $m$ **two-way** passages. The passages are desig",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1000E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of $n$ locations connected by $m$ **two-way** passages. The passages are desig...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你的朋友正在开发一款电脑游戏。他已经决定了游戏世界的结构——它由 $n$ 个地点通过 $m$ 条*双向*通道连接而成。这些通道的设计保证了从任意地点都能到达其他任意地点。\n\n当然，某些通道需要由怪物把守（如果你可以毫无困难地随意通行，那就不有趣了，对吧？）。一些关键通道将由极其可怕的怪物把守，要求英雄做好战斗准备并设计击败它们的战术（通常这类怪物被称为*首领*）。你的朋友希望你帮助他放置这些首领。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected, connected graph with $ |V| = n $, $ |E| = m $, and no multiple edges.\n\nA *bridge* is an edge whose removal increases the number of connected comp...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments