时间 \(\mathcal{O}(\frac{n\sqrt{n}\log n}{\omega})\) 空间 \(\mathcal{O}(\frac{n\log n}{w})\) 的爆标做法。
首先无解当且仅当图联通且无割边。
首先考虑加边的贡献。
一个比较直观的感受就是只会尽可能少的加边，即加边到整个图连通。
证明考虑删掉的边。
如果加多了边导致删除后不会有两个连通块一定不行；如果加多了边后最后分出的还是两个连通块显然加多的边是不必要的。
于是加边的贡献就好算了，因为加的边的数量一定是连通块数 \(-1\)。
接下来考虑删边后的贡献。
显然的是肯定两部分大小越接近 \(\frac{n}{2}\) 越优。
考虑两部分是如何组成的。
能发现除了有一个连通块会被割边拆开，其他的连通块都会整体留下，并且这些连通块可以任意组合（还有一种情况是选的割边是加的边，即就是连通块任意组合，可以与上一种情况一同处理）。
于是就可以想到用背包的形式，得到去掉某一个连通块其他连通块大小的背包，这显然是可以 bitset 优化的。
于是一个想法就是缺一分治，即分治时把一边贡献到递归下去的另一边处理，但复杂度为 \(\mathcal{O}(\frac{n^2\log n}{\omega})\)，还是不太行。
进一步的，考虑到除掉去除的连通块，对于其他的连通块其实只关心其大小。
于是在缺一分治时，实际上只需要考虑对出现过的连通块的大小分治。
具体的，若一种连通块的大小的出现次数 \(c \ge 1\)，就可以先将 \(c - 1\) 个用二进制分组的形式放入背包。
那么缺一分治时，实际上涉及到的元素就是连通块的大小了。
大小的种类数是 \(\mathcal{O}(\sqrt{n})\) 的，所以这部分的复杂度是 \(\mathcal{O}(\frac{n\sqrt{n}\log n}{\omega})\)。
接下来优化求解答案。
考虑到因为连通块大小的和 \(= n\)，所以可以直接暴力枚举划分情况，令其中一个块划分到的大小为 \(x\)，并钦定 \(x\) 所在块大小 \(\ge \lceil\frac{n}{2}\rceil\)，再去找这个大小实际是多少。
那么就是找到最靠前的 \(\ge \lceil\frac{n}{2}\rceil - x\) 的位置。
一个想法是判定一下 \(\lceil\frac{n}{2}\rceil - x\) 是否存在，不存在就用 _Find_next，\(\mathcal{O}(\frac{n^2}{\omega})\)。
但是考虑到当 \(x\) 递增时 \(\lceil\frac{n}{2}\rceil - x\) 是递减的，这个最优的位置是可以继承的，就可以先 _Find_next 问出 \(x = 0\) 的情况，然后扫一遍动态维护。
于是这部分复杂度就是 \(\mathcal{O}(n + \frac{n\sqrt{n}}{w})\)。
最后总时间复杂度 \(\mathcal{O}(\frac{n\sqrt
n\log n}{\omega})\)。
因为分治的每一层都需要开一个 bitset，空间复杂度 \(\mathcal{O}(\frac{n\log n}{\omega})\)。
#include<bits/stdc++.h>
using ll = long long;
inline ll pw2(int n) {return 1ll * n * n;}
const int maxn = 1e5 + 10;
int n;
std::vector<int> to[maxn];
int dfn[maxn], low[maxn], ins[maxn], stk[maxn], top, dtot;
std::vector<int> S;
std::vector<int> vis[maxn];
int tot[maxn];
std::vector<int> val;
int dfs(int u, int fa) {
dfn[u] = low[u] = ++dtot, ins[u] = 1, stk[++top] = u;
int siz = 1;
for (int v : to[u]) {
if (v == fa) continue;
if (! dfn[v]) {
int siz_ = dfs(v, u); low[u] = std::min(low[u], low[v]);
if (low[v] > dfn[u])
S.push_back(siz_);
siz += siz_;
} else if (ins[v])
low[u] = std::min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
int t;
do {
t = stk[top--], ins[t] = 0;
} while (t != u);
}
return siz;
}
std::bitset<maxn> B[20];
ll ans;
void solve(int l, int r, int dep = 0) {
if (l == r) {
int x = val[l], n2 = n + 1 >> 1;
int w = B[dep]._Find_next(n2);
for (int i = 0; i <= x; i++) {
if (n2 >= i && B[dep][n2 - i])
w = n2 - i;
if (vis[x][i] && w < maxn)
ans = std::min(ans, pw2(w + i) + pw2(n - w - i));
}
return ;
}
int mid = (l + r) >> 1;
B[dep + 1] = B[dep];
for (int i = mid + 1; i <= r; i++)
B[dep + 1] |= B[dep + 1] << val[i];
solve(l, mid, dep + 1);
B[dep + 1] = B[dep];
for (int i = l; i <= mid; i++)
B[dep + 1] |= B[dep + 1] << val[i];
solve(mid + 1, r, dep + 1);
}
inline void Main() {
int m, co; scanf("%d%d%d", &n, &m, &co);
for (int i = 1; i <= n; i++)
to[i].clear();
for (int i = 1, x, y; i <= m; i++)
scanf("%d%d", &x, &y), to[x].push_back(y), to[y].push_back(x);
int cnt = 0;
dtot = 0, memset(dfn, 0, sizeof(int) * (n + 1));
for (int i = 1; i <= n; i++)
tot[i] = 0, vis[i].clear();
val.clear();
for (int i = 1; i <= n; i++)
if (! dfn[i]) {
cnt++; int siz = dfs(i, 0);
if (! tot[siz]++)
vis[siz].resize(siz + 1), val.push_back(siz);
for (int x : S)
vis[siz][x] = vis[siz][siz - x] = 1;
vis[siz][0] = vis[siz][siz] = 1;
S.clear();
}
if (cnt == 1) {
bool fl = 0;
for (int i = 1; i < n; i++)
fl |= vis[n][i];
if (! fl)
return puts("-1"), void();
}
B[0].reset(), B[0].set(0);
ans = 1e18;
for (int x = 1; x <= n; x++) {
if (tot[x]) {
val.push_back(x);
int v = tot[x]; v--;
for (int i = 1; i <= v; v -= i, i <<= 1)
B[0] |= B[0] << i * x;
B[0] |= B[0] << v * x;
}
}
solve(0, val.size() - 1);
printf("%lld\n", 1ll * co * (cnt - 1) + ans);
}
int main() {
int T; scanf("%d", &T);
while (T--) Main();
return 0;
}