在硬版本中, $$$2 \leq \sum n \leq 10^5$$$ 和 $$$1 \leq \sum m \leq 5 \times 10^{5}$$$
在摄魂怪组织的工人罢工要求平等权利之后,阿兹卡班监狱受到了一些破坏。安定了灵魂之后,魔法部正在考虑翻新监狱,以确保摄魂怪受到控制。监狱由$$$n$$$牢房和$$$m$$$双向走廊组成。 $$$i^{th}$$$ 走廊是从单元格 $$$u_i$$$ 到 $$$v_i$$$。如果 $$$S$$$ 中的任何单元可从 $$$S$$$ 中的任何其他单元到达,则这些单元 $$$S$$$ 的子集称为复合体。形式上,如果 $$$x$$$ 和 $$$y$$$ 对于 S$$$ 中的所有 $$$x, y 彼此可达,且仅使用来自 $$$S$$$ 的单元格,则单元格 $$$S$$$ 的子集是复数。由 $$$k$$$ 单元组成的复杂 $$$S$$$ 所需的资金定义为 $$$k^2$$$。
作为霍格沃茨魔法室内设计入门课程的一部分,你的任务是设计监狱。魔法部要求你将监狱分成 $$$2$$$ 建筑群,并用 $$$\textbf{恰好一条走廊}$$$ 连接它们,这样摄魂怪就无法组织工会会议。为此,您可以建造双向走廊。在任何 $$$2$$$ 单元之间建造走廊所需的资金为 $$$c$$$。
由于预算削减和与食死徒的持续斗争,您必须找到按照部委要求分割监狱所需的 $$$\textbf{最低总资金}$$$ 或 $$$-1$$$(如果无法分割)。
注:总资金是$$$2$$$综合体和走廊所需资金的总和。如果分割后,两个综合体分别有 $$$x$$$ 和 $$$y$$$ 单元,并且您总共建造了 $$$a$$$ 走廊,则总资金将为 $$$x^2 + y^2 + c \times a$$$。请注意 $$$x+y=n$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行由三个整数 $$$n、m$$$ 和 $$$c$$$ 组成($$$2 \leq n \leq 10^5$$$、$$$1 \leq m \leq 5 \times 10^{5}$$$、$$$1 \leq c \leq 10^9$$$)
$$$m$$$ 行,每行由 2 个整数组成 — $$$u_i, v_i$$$ 表示单元格 $$$u_i$$$ 和 $$$v_i$$$ 之间存在走廊 ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$)
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$5 \times 10^5$$$。
保证任意两个单元格之间最多存在一条走廊。
输出
打印根据部委要求分割监狱所需的 $$$\textbf{最低资金}$$$ 或 $$$-1$$$(如果无法分割)。
示例
输入 #1
4 4 6 5 4 3 2 3 2 4 1 2 4 1 3 1 6 6 2 1 4 2 5 3 6 1 5 3 5 6 5 6 5 7 1 4 2 5 3 6 3 5 6 5 7 5 4 1 4 3 6 3 5 6 5 2 7
输出 #1
-1 20 25 33
注意
在样本输入的第一个测试案例中,没有办法按照部委的要求划分监狱。
在第二个测试用例中,将单元格 $$$1$$$ 和 $$$5$$$ 之间的走廊视为分别由 $$$\{2, 3, 5, 6\}$$$ 和 $$$\{1, 4\}$$$ 单元格组成的 $$$2$$$ 复合体之间的连接。没有修建新的走廊。总资金为 $$$4^2 + 2^2 = 20$$$。您可以验证这是所需的最低资金。
在第三个测试用例中,在 $$$2$$$ 和 $$$4$$$ 之间构建一条走廊。将单元格 $$$1$$$ 和 $$$5$$$ 之间的走廊视为分别由 $$$\{3, 5, 6\}$$$ 和 $$$\{1, 2, 4\}$$$ 单元格组成的 $$$2$$$ 复合体之间的连接。总资金为 $$$3^2 + 3^2 + 7 \times 1 = 25$$$。您可以验证这是所需的最低资金。
在第四个测试用例中,在 $$$2$$$ 和 $$$4$$$ 之间以及 $$$5$$$ 和 $$$7$$$ 之间构建一条走廊。将单元格 $$$5$$$ 和 $$$7$$$ 之间的走廊视为分别由 $$$\{1, 2, 4, 7\}$$$ 和 $$$\{3, 5, 6\}$$$ 单元格组成的 $$$2$$$ 复合体之间的连接。总资金为 $$$4^2 + 3^2 + 4 \times 2 = 33$$$。您可以验证这是所需的最低资金。
请注意,所有测试用例可能有多种方式获得相同的资金,但没有其他部门具有更优化的最低资金。