F. Tourist Reform

Codeforces

IDCF732F

Time4000ms

Memory256MB

Difficulty—

dfs and similargraphs

English · Original

Chinese · Translation

Formal · Original

Berland is a tourist country! At least, it can become such — the government of Berland is confident about this. There are _n_ cities in Berland, some pairs of which are connected by two-ways roads. Each road connects two different cities. In Berland there are no roads which connect the same pair of cities. It is possible to get from any city to any other city using given two-ways roads. According to the reform each road will become one-way. It will be oriented to one of two directions. To maximize the tourist attraction of Berland, after the reform for each city _i_ the value _r__i_ will be calculated. It will equal to the number of cities _x_ for which there is an oriented path from the city _i_ to the city _x_. In other words, _r__i_ will equal the number of cities which can be reached from the city _i_ by roads. The government is sure that tourist's attention will be focused on the minimum value of _r__i_. Help the government of Berland make the reform to maximize the minimum of _r__i_. ## Input The first line contains two integers _n_, _m_ (2 ≤ _n_ ≤ 400 000, 1 ≤ _m_ ≤ 400 000) — the number of cities and the number of roads. The next _m_ lines describe roads in Berland: the _j_\-th of them contains two integers _u__j_ and _v__j_ (1 ≤ _u__j_, _v__j_ ≤ _n_, _u__j_ ≠ _v__j_), where _u__j_ and _v__j_ are the numbers of cities which are connected by the _j_\-th road. The cities are numbered from 1 to _n_. It is guaranteed that it is possible to get from any city to any other by following two-ways roads. In Berland there are no roads which connect the same pair of cities. ## Output In the first line print single integer — the maximum possible value _min_1 ≤ _i_ ≤ _n_{_r__i_} after the orientation of roads. The next _m_ lines must contain the description of roads after the orientation: the _j_\-th of them must contain two integers _u__j_, _v__j_, it means that the _j_\-th road will be directed from the city _u__j_ to the city _v__j_. Print roads in the same order as they are given in the input data. [samples]

贝兰是一个旅游国家！至少，它可以成为这样的国家——贝兰政府对此充满信心。贝兰有 #cf_span[n] 座城市，其中一些城市对通过双向道路相连。每条道路连接两个不同的城市。在贝兰，不存在连接相同城市对的多条道路。任意两座城市之间都可以通过给定的双向道路相互到达。根据改革，每条道路将变为单向道路，方向将被指定为两个可能方向之一。为了最大化贝兰的旅游吸引力，改革后将为每座城市 #cf_span[i] 计算一个值 #cf_span[ri]，它等于满足“存在从城市 #cf_span[i] 到城市 #cf_span[x] 的有向路径”的城市 #cf_span[x] 的数量。换句话说，#cf_span[ri] 表示从城市 #cf_span[i] 出发通过道路可以到达的城市数量。政府确信，游客的关注点将集中在所有 #cf_span[ri] 中的最小值上。请帮助贝兰政府进行道路定向，以最大化所有 #cf_span[ri] 的最小值。第一行包含两个整数 #cf_span[n, m] (#cf_span[2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000]) —— 城市数量和道路数量。接下来的 #cf_span[m] 行描述贝兰的道路：第 #cf_span[j] 行包含两个整数 #cf_span[uj] 和 #cf_span[vj] (#cf_span[1 ≤ uj, vj ≤ n], #cf_span[uj ≠ vj])，表示第 #cf_span[j] 条道路连接的城市编号。城市编号从 #cf_span[1] 到 #cf_span[n]。保证通过双向道路可以从任意城市到达任意其他城市。贝兰中不存在连接相同城市对的重复道路。第一行输出一个整数 —— 道路定向后所有 #cf_span[ri] 的最小值的最大可能值。接下来的 #cf_span[m] 行必须描述定向后的道路：第 #cf_span[j] 行必须包含两个整数 #cf_span[uj, vj]，表示第 #cf_span[j] 条道路的方向是从城市 #cf_span[uj] 指向城市 #cf_span[vj]。请按输入数据的相同顺序输出道路。 ## Input 第一行包含两个整数 #cf_span[n, m] (#cf_span[2 ≤ n ≤ 400 000, 1 ≤ m ≤ 400 000]) —— 城市数量和道路数量。接下来的 #cf_span[m] 行描述贝兰的道路：第 #cf_span[j] 行包含两个整数 #cf_span[uj] 和 #cf_span[vj] (#cf_span[1 ≤ uj, vj ≤ n], #cf_span[uj ≠ vj])，表示第 #cf_span[j] 条道路连接的城市编号。城市编号从 #cf_span[1] 到 #cf_span[n]。保证通过双向道路可以从任意城市到达任意其他城市。贝兰中不存在连接相同城市对的重复道路。 ## Output 第一行输出一个整数 —— 道路定向后所有 #cf_span[ri] 的最小值的最大可能值。接下来的 #cf_span[m] 行必须描述定向后的道路：第 #cf_span[j] 行必须包含两个整数 #cf_span[uj, vj]，表示第 #cf_span[j] 条道路的方向是从城市 #cf_span[uj] 指向城市 #cf_span[vj]。请按输入数据的相同顺序输出道路。 [samples]

**Definitions** Let $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $. Let $ \vec{G} = (V, \vec{E}) $ be an orientation of $ G $, where each edge $ \{u, v\} \in E $ is assigned a direction $ (u \to v) $ or $ (v \to u) $. For each vertex $ i \in V $, define $ r_i $ as the number of vertices reachable from $ i $ in $ \vec{G} $ (including $ i $ itself). **Constraints** 1. $ 2 \leq n \leq 400{,}000 $ 2. $ 1 \leq m \leq 400{,}000 $ 3. $ G $ is connected and simple (no multiple edges or self-loops). **Objective** Maximize $ \min_{1 \leq i \leq n} r_i $ over all possible orientations $ \vec{G} $. Output the maximum possible value of $ \min_i r_i $, and a corresponding orientation of each edge in the order of input.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "F. Tourist Reform",
    "description": {
      "content": "Berland is a tourist country! At least, it can become such — the government of Berland is confident about this. There are _n_ cities in Berland, some pairs of which are connected by two-ways roads. E",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF732F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Berland is a tourist country! At least, it can become such — the government of Berland is confident about this.\n\nThere are _n_ cities in Berland, some pairs of which are connected by two-ways roads. E...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "贝兰是一个旅游国家！至少，它可以成为这样的国家——贝兰政府对此充满信心。\n\n贝兰有 #cf_span[n] 座城市，其中一些城市对通过双向道路相连。每条道路连接两个不同的城市。在贝兰，不存在连接相同城市对的多条道路。任意两座城市之间都可以通过给定的双向道路相互到达。\n\n根据改革，每条道路将变为单向道路，方向将被指定为两个可能方向之一。\n\n为了最大化贝兰的旅游吸引力，改革后将为每座城市 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $.  \nLet $ \\vec{G} = (V, \\vec{E}) $ be an orientation of $ G $, where each edge $ \\{u, v\\} \\in E $ is ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments