在简单版本中,$$$m = n-1$$$,并且对于所有 $$$u、v$$$ ($$$1 \leq u, v \leq n$$$),$$$u$$$ 和 $$$v$$$ 之间存在一条路径。
在摄魂怪组织工人罢工要求平等权利后,阿兹卡班监狱受到了一些破坏。安定了灵魂之后,魔法部正在考虑翻新监狱,以确保摄魂怪受到控制。监狱由$$$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$$$, $$$m = n - 1$$$, $$$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
2 2 1 3 1 2 8 7 76 3 1 3 2 2 4 2 5 4 6 4 7 7 8
输出 #1
2 32