English · Original
Chinese · Translation
Formal · Original
Hongcow is ruler of the world. As ruler of the world, he wants to make it easier for people to travel by road within their own countries.
The world can be modeled as an undirected graph with _n_ nodes and _m_ edges. _k_ of the nodes are home to the governments of the _k_ countries that make up the world.
There is at most one edge connecting any two nodes and no edge connects a node to itself. Furthermore, for any two nodes corresponding to governments, **there is no path between those two nodes**. Any graph that satisfies all of these conditions is _stable_.
Hongcow wants to add as many edges as possible to the graph while keeping it stable. Determine the maximum number of edges Hongcow can add.
## Input
The first line of input will contain three integers _n_, _m_ and _k_ (1 ≤ _n_ ≤ 1 000, 0 ≤ _m_ ≤ 100 000, 1 ≤ _k_ ≤ _n_) — the number of vertices and edges in the graph, and the number of vertices that are homes of the government.
The next line of input will contain _k_ integers _c_1, _c_2, ..., _c__k_ (1 ≤ _c__i_ ≤ _n_). These integers will be pairwise distinct and denote the nodes that are home to the governments in this world.
The following _m_ lines of input will contain two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_). This denotes an undirected edge between nodes _u__i_ and _v__i_.
It is guaranteed that the graph described by the input is stable.
## Output
Output a single integer, the maximum number of edges Hongcow can add to the graph while keeping it stable.
[samples]
## Note
For the first sample test, the graph looks like this:
<center></center>Vertices 1 and 3 are special. The optimal solution is to connect vertex 4 to vertices 1 and 2. This adds a total of 2 edges. We cannot add any more edges, since vertices 1 and 3 cannot have any path between them.For the second sample test, the graph looks like this:
<center></center>We cannot add any more edges to this graph. Note that we are not allowed to add self-loops, and the graph must be simple.
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 $, each representing a government.
**Given:**
- $ G $ is stable:
(i) No self-loops or multiple edges.
(ii) For any two distinct government nodes $ c_i, c_j \in C $, $ i \ne j $, there is **no path** between them.
→ Thus, the $ k $ government nodes lie in **distinct connected components**.
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 = V \setminus \bigcup_{i=1}^k C_i $ be the set of non-government nodes (if any), which may be distributed among the $ k $ components.
Let $ n_i = |C_i| $, the number of vertices in component $ C_i $, for $ i = 1, \dots, k $. Then:
$$
\sum_{i=1}^k n_i = n
$$
**Objective:**
Maximize the number of edges that can be added while preserving stability.
**Constraints for stability after adding edges:**
- No edge may be added between any two government nodes (already satisfied by distinct components).
- No path may be created between any two government nodes → **No merging of components**.
- Therefore, edges may only be added **within** each connected component.
In a connected component of size $ n_i $, the maximum number of edges possible in a simple undirected graph is $ \binom{n_i}{2} $.
Currently, component $ C_i $ has $ m_i $ edges (unknown individually, but total $ \sum m_i = m $).
So, the maximum number of edges that can be added to component $ C_i $ is:
$$
\binom{n_i}{2} - m_i
$$
Total maximum edges that can be added:
$$
\sum_{i=1}^k \left( \binom{n_i}{2} - m_i \right) = \left( \sum_{i=1}^k \binom{n_i}{2} \right) - m
$$
**Therefore, the answer is:**
$$
\boxed{\sum_{i=1}^k \binom{n_i}{2} - m}
$$
where $ n_i $ is the size of the connected component containing the $ i $-th government node.
API Response (JSON)
{
"problem": {
"name": "C. Hongcow Builds A Nation",
"description": {
"content": "Hongcow is ruler of the world. As ruler of the world, he wants to make it easier for people to travel by road within their own countries. The world can be modeled as an undirected graph with _n_ node",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF745C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Hongcow is ruler of the world. As ruler of the world, he wants to make it easier for people to travel by road within their own countries.\n\nThe world can be modeled as an undirected graph with _n_ node...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Hongcow 是世界的统治者。作为世界的统治者，他希望让人民更容易在自己国家内部通过公路旅行。\n\n世界可以建模为一个具有 #cf_span[n] 个节点和 #cf_span[m] 条边的无向图。#cf_span[k] 个节点分别是构成这个世界 #cf_span[k] 个国家的政府所在地。\n\n任意两个节点之间至多有一条边，且没有边连接节点到自身。此外，对于任意两个代表政府的节点，它们之间不存在路径...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "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 $, each representing a government.\n\n**Given:**\n- $ ...",
"is_translate": false,
"language": "Formal"
}
]
}