A. Hongcow Builds A Nation

Hongcow 是世界的统治者。作为世界的统治者，他希望让人民更容易在本国境内通过公路旅行。 世界可以建模为一个具有 #cf_span[n] 个节点和 #cf_span[m] 条边的无向图。#cf_span[k] 个节点是构成世界的 #cf_span[k] 个国家政府的所在地。 任意两个节点之间至多有一条边，且没有边连接节点到自身。此外，对于任意两个代表政府的节点，*这两个节点之间不存在路径*。满足所有这些条件的图称为 _稳定_ 图。 Hongcow 希望在保持图稳定的前提下，尽可能多地添加边。请确定 Hongcow 最多能添加多少条边。 输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 1 000], #cf_span[0 ≤ m ≤ 100 000], #cf_span[1 ≤ k ≤ n]）—— 分别表示图中的顶点数、边数和政府所在地的顶点数。 第二行包含 #cf_span[k] 个整数 #cf_span[c1, c2, ..., ck]（#cf_span[1 ≤ ci ≤ n]）。这些整数互不相同，表示世界中政府所在地的节点。 接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示节点 #cf_span[ui] 和 #cf_span[vi] 之间的一条无向边。 保证输入描述的图是稳定的。 请输出一个整数，表示在保持图稳定的前提下，Hongcow 最多能添加的边数。 对于第一个样例测试，图如下所示： 对于第二个样例测试，图如下所示： ## Input 输入的第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 1 000], #cf_span[0 ≤ m ≤ 100 000], #cf_span[1 ≤ k ≤ n]）—— 分别表示图中的顶点数、边数和政府所在地的顶点数。第二行包含 #cf_span[k] 个整数 #cf_span[c1, c2, ..., ck]（#cf_span[1 ≤ ci ≤ n]）。这些整数互不相同，表示世界中政府所在地的节点。接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n]），表示节点 #cf_span[ui] 和 #cf_span[vi] 之间的一条无向边。保证输入描述的图是稳定的。 ## Output 请输出一个整数，表示在保持图稳定的前提下，Hongcow 最多能添加的边数。 [samples] ## Note 对于第一个样例测试，图如下所示： 顶点 #cf_span[1] 和 #cf_span[3] 是特殊的。最优解是将顶点 #cf_span[4] 连接到顶点 #cf_span[1] 和 #cf_span[2]。这样共添加了 #cf_span[2] 条边。我们不能再添加更多边，因为顶点 #cf_span[1] 和 #cf_span[3] 之间不能存在任何路径。 对于第二个样例测试，图如下所示： 我们不能再向该图添加任何边。注意，我们不允许添加自环，且图必须是简单图。

Let $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, and $ k $ distinguished vertices $ C = \{c_1, c_2, \dots, c_k\} \subseteq V $, called *government nodes*. The graph is stable if: 1. There are no self-loops or multiple edges. 2. No two government nodes are connected by any path (i.e., each government node lies in a distinct connected component). Let $ \mathcal{C} = \{C_1, C_2, \dots, C_k\} $ be the connected components of $ G $, each containing exactly one government node (by stability). Let $ s_i = |C_i| $ denote the size of component $ C_i $, for $ i = 1, 2, \dots, k $. Let $ r = n - \sum_{i=1}^k s_i $ be the number of non-government nodes not in any $ C_i $ (i.e., isolated nodes not connected to any government node). **Goal:** Maximize the number of edges that can be added while preserving stability. To maximize edges under stability: - Within each component $ C_i $, we may add all possible edges to make it a complete graph: $ \binom{s_i}{2} - e_i $, where $ e_i $ is the current number of edges in $ C_i $. - We may also add edges between non-government isolated nodes and any component $ C_i $, but **not** between different government components. - We may connect the $ r $ isolated nodes among themselves, and to any single component, but **not** connect them across components (to preserve separation of government nodes). - To maximize total edges, we should merge all $ r $ isolated nodes into the **largest** component (since complete graphs maximize edges per node count). Thus, define: - $ s_{\max} = \max_{1 \leq i \leq k} s_i $ - Merge all $ r $ isolated nodes into the largest component: new size = $ s_{\max} + r $ - The other $ k-1 $ components remain unchanged. Now, total possible edges in a stable graph is: $$ \sum_{i=1}^k \binom{s_i'}{2} $$ where $ s_i' = s_i $ for all $ i $ except the largest, where $ s_{\max}' = s_{\max} + r $. Current number of edges is $ m $. Thus, maximum edges that can be added is: $$ \left( \binom{s_{\max} + r}{2} + \sum_{\substack{i=1 \\ s_i \ne s_{\max}}}^k \binom{s_i}{2} \right) - m $$ Let $ S = \sum_{i=1}^k s_i $, so $ r = n - S $. Then: $$ \boxed{ \left( \binom{s_{\max} + n - S}{2} + \sum_{\substack{i=1 \\ s_i \ne s_{\max}}}^k \binom{s_i}{2} \right) - m } $$