省流：弘文。
一共四个题。大概开考后 20min 过了 T1, T2, T3。然后仔细想了想发现 T2 读错题了。改了 30min 才改出来，中间去水了一会 QQ。
然后想 T4，很快想出解法，然后开始写了。
然后一直写到比赛结束，写了 5K？？？？？为了防止自己以后再犯这种神志不清的错误，这里放一下考场错误仅有 15pts 代码来警示自己。
/*
Solution:*/
#include <bits/stdc++.h>using ll = long long;
using ull = unsigned long long;
//using i28 = __int128_t;
//using u28 = __uint128_t;
using ldb = long double;#define int long long
#define max(x, y) (x > y ? x : y)
#define min(x, y) (x < y ? x : y)
#define abs(x) (x < 0 ? -x : x)constexpr int N = 5e5 + 10;
int n, m, Xcnt, q;int anc[N], sz[N];
int find(int u) {if (anc[u] == u) return u;else return anc[u] = find(anc[u]);
}
void merge(int u, int v) {u = find(u), v = find(v);if (u != v) sz[v] += sz[u], anc[u] = v;
}int rid[N];
struct node {int sz; std::vector <int> vec;bool operator < (const node &cmp) const {return sz > cmp.sz; }
} a[N];
std::vector <int> vec[N]; signed main() {
// freopen(".in", "r", stdin), freopen(".out", "w", stdout);std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> m >> Xcnt >> q;for (int i = 1; i <= n; ++i) {anc[i] = i, sz[i] = 1; }while (q --> 0) {int _u, _v; std::cin >> _u >> _v;merge(_v, _u); }if (m > (n - 1) * n) {return std::cout << "-1\n", 0; }int tmp = 0, tmp2 = 0, tot = 0;for (int i = 1; i <= n; ++i) if (find(i) == i) {tmp += (sz[i] == 1 ? 0 : sz[i]), a[++tot].sz = sz[i], rid[i] = tot, a[tot].vec.emplace_back(i);} else a[rid[find(i)]].vec.emplace_back(i);if (tmp > m || tot < Xcnt) {return std::cout << "-1\n", 0; } m -= tmp; std::sort(a + 1, a + 1 + tot);if (m < 0) {return std::cout << "-1", 0;}// merge to Xcnt connected blocks with no cost
// for (int i = 1; i <= tot; ++i) {
// std::cout << a[i].sz << " : "; for (auto j : a[i].vec) std::cout << j << " "; std::cout << "\n";
// }int new_sz = a[1].sz;std::vector <int> new_vec = a[1].vec; for (int i = 2; i <= tot - Xcnt + 1; ++i) { // merge i and i - 1if (new_sz == 1) --m; if (a[i].sz == 1) --m; new_sz += a[i].sz;for (auto j : a[i].vec) new_vec.emplace_back(j);
// std::cout << i << "\n";}if (m < 0) return std::cout << "-1\n", 0;a[1].sz = new_sz, a[1].vec = new_vec;int pos = 1; for (int i = tot - Xcnt + 2; i <= tot; ++i) a[++pos] = a[i];for (int i = Xcnt + 1; i <= tot; ++i) a[i].sz = 0, a[i].vec.clear(); // std::cout << m << "\n";
// for (int i = 1; i <= Xcnt; ++i) {
// std::cout << a[i].sz << " : ";
//// for (auto j : a[i].vec) std::cout << j << " "; std::cout << "\n";
// for (int j = 0; j < a[i].vec.size(); ++j) std::cout << a[i].vec[j] << " "; std::cout << "\n";
// }
// std::cout << m << "\n";// checktmp = 0;int tmpm = m; for (int i = 1; i <= Xcnt; ++i) {int cur = (a[i].sz - 1) * a[i].sz - a[i].sz;tmpm -= cur; }int cursz = a[1].sz;for (int i = 2; i <= Xcnt; ++i) {int cur = cursz * a[i].sz;tmpm -= cur, cursz += a[i].sz; }if (tmpm > 0) {return std::cout << "-1\n", 0; }//for (int i = 1; i <= Xcnt; ++i) {for (int j = 0; j < a[i].vec.size() - 1; ++j) {std::cout << a[i].vec[j] << " " << a[i].vec[j + 1] << "\n"; }if (a[i].sz > 1) std::cout << a[i].vec.back() << " " << a[i].vec.front() << "\n"; }for (int i = 1; i <= Xcnt; ++i) {int cur = (a[i].sz - 1) * a[i].sz - a[i].sz;if (m <= cur) {for (int j = 1; j < i; ++j) {for (int k = 0; k < a[j].vec.size(); ++k) for (int h = 0; h < a[j].vec.size(); ++h) if (k != h) {if (h == k + 1) continue ;if (k == 0 && h == a[j].vec.size() - 1) continue ; std::cout << a[j].vec[k] << " " << a[j].vec[h] << "\n"; }}int p = 0;while (m > 0) {for (int j = 0; j < a[i].vec.size(); ++j)if (p != j) {if (p != j + 1 && !(j == a[i].vec.size() - 1 && p == 0)) {std::cout << a[i].vec[j] << " " << a[i].vec[p] << "\n";--m;if (m == 0) break ; }if (j != p + 1 && !(p == a[i].vec.size() - 1 && j == 0)) {std::cout << a[i].vec[p] << " " << a[i].vec[j] << "\n";--m; if (m == 0) break ; }}++p; }return 0; }m -= cur; }int cur_sz = a[1].sz;for (int i = 2; i <= Xcnt; ++i) { // merge i and i - 1int add = a[i].sz * cur_sz;if (m <= add) {std::vector <int> ans;for (int j = 1; j <= Xcnt; ++j) {for (int k = 0; k < a[j].vec.size(); ++k) for (int h = 0; h < a[j].vec.size(); ++h) if (h != k) {if (h != k + 1 && !(k == a[j].vec.size() - 1 && h == 0)) std::cout << a[j].vec[k] << " " << a[j].vec[h] << "\n";if (k != h + 1 && !(h == a[j].vec.size() - 1 && k == 0)) std::cout << a[j].vec[h] << " " << a[j].vec[k] << "\n";}}for (int j = 1; j < i; ++j) for (auto k : a[j].vec) ans.emplace_back(k);
// for (auto j : ans) for (auto k : ans) if (j != k) std::cout << j << " " << k << "\n";for (int j = 1; j < i; ++j) {for (int k = j + 1; k < i; ++k)for (auto a1 : a[j].vec) for (auto a2 : a[j].vec) std::cout << a1 << " " << a2 << "\n"; }int p = 0; while (m > 0) {for (auto j : a[i].vec) {std::cout << ans[p] << " " << j << "\n";--m; if (m == 0) break ; std::cout << j << " " << ans[p] << "\n"; --m; } ++p; }return 0;} m -= add, cur_sz += a[i].sz; }std::cout << "-1\n"; return 0;
}大概是不知道自己写了什么。
比赛成绩出来是 \(100 + 90 + 100 + 15\)，预计是 \(100 + 100 + 100 + [0, 100]\)。自闭了。