[PA 2020] Trzy drogi

Luogu

IDLGP9105

Time8000ms

Memory512MB

DifficultyP7

2020PA（波兰）

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Trzy drogi](https://sio2.mimuw.edu.pl/c/pa-2020-1/trz/)** Byteur 国王，Byteotia 的统治者，梦想着征服 Bitotia。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来后情况就有些不同。 Byteotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $m$ 条双向道路连接。每条路都连接着两个不同的城市，但也可能有多条道路连接着同一对城市的情况。从任何城市出发，经过一条或多条道路可以到达其他任意城市。国王想知道，如果 Bitotia 进攻 Byteotia，从现有的 $m$ 条道路中毁掉三条，会发生什么，将严重损害该国的通信的可能性有多大？你的任务是找出答案！数一数有多少条这样的三条路，在这些路被毁之后，至少有一对城市不可以通过剩余的道路互相到达对方。 ## Input 第一行包含两个整数 $n,m$，分别表示 Byteotia 的城市个数和道路条数。接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示城市 $a_i$ 和 $b_i$ 之间被一条道路连接。你可以假设从任何城市出发，经过一条或多条道路可以到达其他任意城市。 ## Output 输出一行一个整数，表示移除这三条路，至少存在两个城市彼此不可达的无序三元组的个数。 [samples] ## Note #### 样例 1 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/ew3z3u7s.png) 请注意，例如移除第 $3,5,7$ 条路后，Byteotia 会被分为多于两部分，但这样的三元组只能被计算一次。 ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$，$3\le m\le 5\times 10^5$，$1\le a_i,b_i\le n$，$a_i\neq b_i$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2020] Trzy drogi",
    "description": {
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Trzy drogi](https://sio2.mimuw.edu.pl/c/pa-2020-1/trz/)** Byteur 国王，Byteotia 的统治者，梦想着征服 Bitotia。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9105"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Trzy drogi](https://sio2.mimuw.edu.pl/c/pa-2020-1/trz/)**\n\nByteur 国王，Byteotia 的统治者，梦想着征服 Bitotia。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments