题目分析

本题要求我们在一个有向图上，通过特定的操作（"友好条约缔结会议"）来添加尽可能多的边。操作规则是：如果存在一个国家 $x$，它同时向 $p$ 和 $q$ 派遣了大使（即存在边 $(x,p)$ 和 $(x,q)$），那么 $p$ 和 $q$ 可以开会，开会后会添加双向边 $(p,q)$ 和 $(q,p)$（如果这些边已存在则不重复添加）。

核心思路

这个问题可以转化为图论中的连通分量分析问题：

1. 中介国的角色：如果一个国家 $x$ 有出边指向 $p$ 和 $q$，那么 $x$ 可以作为 $p$ 和 $q$ 会议的中介。这意味着所有被同一个国家指向的国家之间都可能建立连接。

2. 双向边的传播效应：一旦两个国家通过会议建立了双向连接，这个连接会产生连锁反应。如果 $p$ 和 $q$ 已经双向连通，那么任何指向 $p$ 的国家也可以作为 $q$ 与其他国家会议的中介，反之亦然。

3. 强连通分量（SCC）：通过分析，我们发现最终能够达到的状态是：在同一个强连通分量内的所有国家之间都会建立完整的双向边网络。也就是说，如果一组国家通过一系列会议操作能够相互连接（直接或间接），那么这组国家最终会形成一个完全图（每个点都与其他所有点有双向边）。

4. 分量合并：如果两个强连通分量之间存在一个中介国，它同时指向这两个分量中的某些国家，那么这两个分量最终会合并成一个更大的强连通分量。

算法步骤

1. 构建图模型：将原有关系统计为有向图。

2. 寻找强连通分量：使用 Tarjan 算法或 Kosaraju 算法找出所有的强连通分量。

3. 分量合并分析：对于每个国家 $x$，检查它指向的所有国家。如果这些国家属于不同的强连通分量，那么这些分量可以通过 $x$ 合并。

4. 计算最大边数：对于最终形成的每个连通块（可能是合并后的强连通分量），如果块大小为 $k$，那么该块内最多有 $k \times (k-1)$ 条有向边（即完全图）。将所有这样的块边数相加，再加上原有的不同块之间的边（这些边在操作过程中不会被删除），即为最终答案。

关键点

• 操作的本质是在有共同"朋友"（中介国）的国家之间建立双向连接
• 这个过程具有传递性，最终会形成若干个强连通分量
• 强连通分量之间如果有共同的中介国，还会进一步合并
• 最终每个连通块内部会形成完全图，块间的原有边保留

复杂度分析

使用 Tarjan 算法求强连通分量的时间复杂度为 $O(N+M)$，后续的合并和计算过程也可以在近似线性时间内完成，因此总体复杂度为 $O(N+M)$，能够处理题目给出的数据规模（$N \leq 10^5, M \leq 2\times 10^5$）。