考虑增量构造第一个集合。首先令 \(S = \{1\}\)，然后不断找到下一个点 \(u\)，使得它在抠掉 \(S\) 的图上不是割点，并且与 \(S\) 连通。然后令 \(S \gets S \cup \{u\}\)。
可以证明一定能找到这样的 \(u\)。
因为对于抠掉 \(S\) 的新图上，若存在割点 \(v\)，那么删除 \(v\) 后的每一个连通块都与 \(S\) 连通，否则与题目原图没有割点的条件矛盾。
所以我们能找到一个割点 \(w\) 使得 dfs 树上它存在一棵子树没有割点。由上一定能在这棵子树找到一个与 \(S\) 连通的点。
综上所述一定能找到这样的 \(u\)。
时间复杂度 \(O(n(n + m))\)。
code
// Problem: F. Group Division
// Contest: Codeforces - Good Bye 2023
// URL: https://codeforces.com/contest/1916/problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 4040;
int n, n1, n2, m;
bool vis[maxn], cut[maxn];
vector<int> G[maxn];
int low[maxn], dfn[maxn], tim;
void dfs(int u, int fa) {
low[u] = dfn[u] = ++tim;
cut[u] = 0;
int cnt = 0;
for (int v : G[u]) {
if (v == fa || vis[v]) {
continue;
}
if (!dfn[v]) {
dfs(v, u);
++cnt;
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
cut[u] = 1;
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (cut[u] && fa == -1 && cnt == 1) {
cut[u] = 0;
}
}
void solve() {
scanf("%d%d%d", &n1, &n2, &m);
n = n1 + n2;
for (int i = 1; i <= n; ++i) {
vector<int>().swap(G[i]);
vis[i] = 0;
}
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
vis[1] = 1;
for (int _ = 1; _ < n1; ++_) {
for (int i = 1; i <= n; ++i) {
low[i] = dfn[i] = 0;
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) {
continue;
}
tim = 0;
dfs(i, -1);
break;
}
for (int i = 1; i <= n; ++i) {
if (vis[i] || cut[i]) {
continue;
}
bool fl = 0;
for (int j : G[i]) {
fl |= vis[j];
}
if (fl) {
vis[i] = 1;
break;
}
}
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) {
printf("%d ", i);
}
}
putchar('\n');
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
printf("%d ", i);
}
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}