Description

你是活跃在历史的幕后的一名特工, 为了世界的和平而日以继夜地努力着.

这个世界有 \(n\) 个国家, 编号为 \(1, 2, \ldots, n\), 你的目的是在这 \(n\) 个国家之间建立尽可能多的友好关系. 你为了制定一个特工工作的计划, 作出了一张当今国际关系的 示意图. 你准备了一张非常大的画纸, 先画下了代表每个国家的 \(n\) 个点. 接下来, 为了 表示现在的国际关系, 画下了 \(m\) 个连接两个国家的有向边, 其中从国家 \(a\) 连向国家 \(b\) 的有向边 (下面称作 “边 \((a, b)\)” ) 表示 现在国家 \(a\) 向国家 \(b\) 派遣了大使. 这样就做出了 \(n\) 个点 \(m\) 条边的当今国际关系示意图. 作为两国友好关系的开端, 两国 之间需要进行 友好条约缔结会议 (以下简称会议). 如果某两个国家 \(p\) 和 \(q\) 要进行会议, 那么需要一个向两国都派遣了大使的国家 \(x\) 作为中介. 会议结束后, 会议的双方相互向对方的国家派遣大使. 换句话说, 为了让国 \(p\) 和国 \(q\) 进行会议, 必须存在 一个国家 \(x\) 满足边 \((x, p)\) 和边 \((x, q)\) 都存在, 并且在会议后添加两条边 \((p, q)\) 和\((q, p)\) (如果需要添加的某条边已经存在则不添加). 你的工作是对于可以进行会议的 两国, 选择会议的中介并促使会议进行. 使用这张图进行工作的模拟的话, 世界距离和平 还有多远的一个重要的基准就是这张图上的边数. 也就是说, 你想知道反复进行【选择两个 国家使其进行会议】的工作后, 图上的边数最多会到达多少. 现在给出国家的个数以及当今国际关系的情报, 请你求出反复进行【选择两个国家使其进行会议】的工作后, 图上的边数最多会到达多少.

Input

第一行两个空格分隔的整数 \(n\) 和 \(m\), 分别表示世界上国家的个数和图中的边数接下来 \(m\) 行描述画纸上的有向边的信息, 其中第 \(i\) 行 \((1 \leq i \leq m)\) 有两个空格分隔的整数 \(A_i\) 和 \(B_i\), 表示图中有一条从 \(A_i\) 到 \(B_i\) 的有向边 (即 \(A_i\) 国向 \(B_i\) 国派遣了大使).

Output

输出一行一个整数, 表示能实现的边数的最大值. 注意这个边数包括原有的边数和新连接的 边数.

Sample Input

5 4
1 2
1 3
4 3
4 5

Sample Output

10

Data Range

对于所有数据, 满足:\(1 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5\), 并且满足:\(1 \leq A_i, B_i \leq n, A_i \neq B_i, (A_i, B_i) \neq (A_j, B_j) (i \neq j)\).

Explanation

我们就把他看作一道图论题来做了, 然后把题目元素直接抛下不管就可以了.

首先有这样两个性质:

  1. 若 \(\exists (a, b), (b, a), (b, c), (c, b)\), 则一定可以构造这样两条边 \((a, c), (c, a)\). 也就是说任意多的无向边相连之后, 它们之间一定可以通过某种方式 互相连接成为完全子图.
  2. 若某个点 \(x\) 的入度为 \(0\), 则其指向的点之间可以互相连接.

用并查集维护一下无向边然后统计一下就可以了.

记得双向边判断要用 set, 直接邻接链表会 TLE.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 100100;

class DisjointSet
{
public:
    int n, par[maxn], size[maxn];
    int find(int p)
    {
        if (par[p] == p)
            return p;
        return par[p] = find(par[p]);
    }
    void join(int p, int q)
    {
        p = find(p);
        q = find(q);
        if (p == q) return ;
        par[p] = q;
        size[q] += size[p];
        return ;
    }
    void init(int n_)
    {
        n = n_;
        for (int i = 1; i <= n; i++)
            par[i] = i, size[i] = 1;
        return ;
    }
} djs;

set<int> edges[maxn];
typedef set<int> si;
typedef si::iterator sii;

int n, m;
bool vis[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        edges[a].insert(b);
    }
    djs.init(n);
    // Determining connected components
    for (int i = 1; i <= n; i++)
        for (sii j = edges[i].begin(); j != edges[i].end(); j++)
            if (edges[*j].find(i) != edges[*j].end())
                djs.join(i, *j);
    // Joining subconnections
    for (int i = 1; i <= n; i++)
        if (edges[i].size() > 1)
            for (sii j = ++edges[i].begin(); j != edges[i].end(); j++)
                djs.join(*j, *edges[i].begin());
    // Breadth-first searching
    queue<int> que;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
        if (djs.size[djs.find(i)] > 1) {
            vis[i] = true;
            que.push(i);
        }
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        for (sii j = edges[p].begin(); j != edges[p].end(); j++) {
            djs.join(p, *j);
            if (!vis[*j]) {
                vis[*j] = true;
                que.push(*j);
            }
        }
    }
    // Getting results
    lli res = 0;
    for (int i = 1; i <= n; i++)
        if (djs.find(i) == i) {
            if (djs.size[i] <= 1) {
                res += edges[i].size();
            } else {
                res += (lli)djs.size[i] * (djs.size[i] - 1);
            }
        }
    printf("%lld\n", res);
    return 0;
}