311333: CF1970G1. Min-Fund Prison (Easy)

G1. Min-Fund Prison (Easy)time limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

In the easy version, $m = n-1$ and there exists a path between $u$ and $v$ for all $u, v$ ($1 \leq u, v \leq n$).

After a worker's strike organized by the Dementors asking for equal rights, the prison of Azkaban has suffered some damage. After settling the spirits, the Ministry of Magic is looking to renovate the prison to ensure that the Dementors are kept in check. The prison consists of $n$ prison cells and $m$ bi-directional corridors. The $i^{th}$ corridor is from cells $u_i$ to $v_i$. A subset of these cells $S$ is called a complex if any cell in $S$ is reachable from any other cell in $S$. Formally, a subset of cells $S$ is a complex if $x$ and $y$ are reachable from each other for all $x, y \in S$, using only cells from $S$ on the way. The funding required for a complex $S$ consisting of $k$ cells is defined as $k^2$.

As part of your Intro to Magical Interior Design course at Hogwarts, you have been tasked with designing the prison. The Ministry of Magic has asked that you divide the prison into $2$ complexes with $\textbf{exactly one corridor}$ connecting them, so that the Dementors can't organize union meetings. For this purpose, you are allowed to build bi-directional corridors. The funding required to build a corridor between any $2$ cells is $c$.

Due to budget cuts and the ongoing fight against the Death Eaters, you must find the $\textbf{minimum total funding}$ required to divide the prison as per the Ministry's requirements or $-1$ if no division is possible.

Note: The total funding is the sum of the funding required for the $2$ complexes and the corridors built. If after the division, the two complexes have $x$ and $y$ cells respectively and you have built a total of $a$ corridors, the total funding will be $x^2 + y^2 + c \times a$. Note that $x+y=n$.

Input

The first line contains one integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case consists of three integers $n, m$ and $c$ ($2 \leq n \leq 10^5$, $m = n - 1$, $1 \leq c \leq 10^9$)

$m$ lines follow, each consisting of 2 integers — $u_i, v_i$ indicating a corridor is present between cells $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$)

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $5 \times 10^5$.

It is guaranteed that there exists at most one corridor between any two cells.

Output

Print the $\textbf{minimum funding}$ required to divide the prison as per the Ministry's requirements or $-1$ if no division is possible.

ExampleInput

2
2 1 3
1 2
8 7 76
3 1
3 2
2 4
2 5
4 6
4 7
7 8

Output

2
32

题目大意：
这个题目是关于将阿兹卡班监狱分成两个复合体的问题，以便阻止摄魂怪组织工会会议。监狱由n个单元格和m个双向走廊组成。一个单元格的子集S被称为复合体，如果S中的任何一个单元格都可以从S中的其他任何单元格到达。正式来说，如果对于所有的x, y属于S，x和y可以通过只经过S中的单元格相互到达，那么单元格的子集S就是一个复合体。由k个单元格组成的复合体S所需的资金定义为k^2。你需要将监狱分成两个复合体，这两个复合体之间恰好有一个走廊连接，以防止摄魂怪组织工会会议。为了这个目的，你可以建造双向走廊。建造任意两个单元格之间的走廊所需的资金是c。由于预算削减和对抗食死徒的持续战斗，你必须找到按照部里的要求划分监狱所需的最小总资金，如果没有可能的划分，则返回-1。

输入数据格式：
输入的第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。然后是t个测试用例。
每个测试用例的第一行包含三个整数n、m和c（2≤n≤10^5，m=n-1，1≤c≤10^9）
接下来m行，每行包含2个整数——u_i, v_i，表示单元格u_i和v_i之间存在一个走廊（1≤u_i, v_i≤n，u_i≠v_i）
保证所有测试用例的n之和不超过10^5。
保证所有测试用例的m之和不超过5×10^5。
保证任意两个单元格之间最多只有一个走廊。

输出数据格式：
打印按照部里的要求划分监狱所需的最小资金，如果没有可能的划分，则返回-1。

例：
输入：
2
2 1 3
1 2
8 7 76
3 1
3 2
2 4
2 5
4 6
4 7
7 8
输出：
2
32题目大意： 这个题目是关于将阿兹卡班监狱分成两个复合体的问题，以便阻止摄魂怪组织工会会议。监狱由n个单元格和m个双向走廊组成。一个单元格的子集S被称为复合体，如果S中的任何一个单元格都可以从S中的其他任何单元格到达。正式来说，如果对于所有的x, y属于S，x和y可以通过只经过S中的单元格相互到达，那么单元格的子集S就是一个复合体。由k个单元格组成的复合体S所需的资金定义为k^2。你需要将监狱分成两个复合体，这两个复合体之间恰好有一个走廊连接，以防止摄魂怪组织工会会议。为了这个目的，你可以建造双向走廊。建造任意两个单元格之间的走廊所需的资金是c。由于预算削减和对抗食死徒的持续战斗，你必须找到按照部里的要求划分监狱所需的最小总资金，如果没有可能的划分，则返回-1。 输入数据格式： 输入的第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。然后是t个测试用例。 每个测试用例的第一行包含三个整数n、m和c（2≤n≤10^5，m=n-1，1≤c≤10^9） 接下来m行，每行包含2个整数——u_i, v_i，表示单元格u_i和v_i之间存在一个走廊（1≤u_i, v_i≤n，u_i≠v_i） 保证所有测试用例的n之和不超过10^5。 保证所有测试用例的m之和不超过5×10^5。 保证任意两个单元格之间最多只有一个走廊。 输出数据格式： 打印按照部里的要求划分监狱所需的最小资金，如果没有可能的划分，则返回-1。 例： 输入： 2 2 1 3 1 2 8 7 76 3 1 3 2 2 4 2 5 4 6 4 7 7 8 输出： 2 32