{"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。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来后情况就有些不同。\n\nByteotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $m$ 条双向道路连接。每条路都连接着两个不同的城市，但也可能有多条道路连接着同一对城市的情况。从任何城市出发，经过一条或多条道路可以到达其他任意城市。\n\n国王想知道，如果 Bitotia 进攻 Byteotia，从现有的 $m$ 条道路中毁掉三条，会发生什么，将严重损害该国的通信的可能性有多大？你的任务是找出答案！数一数有多少条这样的三条路，在这些路被毁之后，至少有一对城市不可以通过剩余的道路互相到达对方。\n\n## Input\n\n第一行包含两个整数 $n,m$，分别表示 Byteotia 的城市个数和道路条数。\n\n接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示城市 $a_i$ 和 $b_i$ 之间被一条道路连接。\n\n你可以假设从任何城市出发，经过一条或多条道路可以到达其他任意城市。\n\n## Output\n\n输出一行一个整数，表示移除这三条路，至少存在两个城市彼此不可达的无序三元组的个数。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ew3z3u7s.png)\n\n请注意，例如移除第 $3,5,7$ 条路后，Byteotia 会被分为多于两部分，但这样的三元组只能被计算一次。\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9105","tags":["2020","PA（波兰）"],"sample_group":[["8 11\n2 3\n4 5\n3 1\n3 2\n5 7\n3 6\n1 2\n3 4\n6 5\n8 7\n7 8","103"]],"created_at":"2026-03-03 11:09:25"}}