P14219 [ICPC 2024 Kunming I] 阻止城堡 2

#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<int, int> pii;

const int maxn = 1000100;
const int inf = 0x3f3f3f3f;

int n, m, K, hd[maxn], nt, S, T, len, id1[maxn], id2[maxn], e[maxn];
bool vis[maxn], mk1[maxn], mk2[maxn];
pii c[maxn];

struct node {
	int x, y;
} a[maxn], b[maxn];

struct edge {
	int to, next, cap, flow;
} edges[maxn << 1];

inline void add_edge(int u, int v, int c, int f) {
	edges[++len].to = v;
	edges[len].next = hd[u];
	edges[len].cap = c;
	edges[len].flow = f;
	hd[u] = len;
}

struct Dinic {
	int cur[maxn], d[maxn];
	bool vis[maxn];
	
	inline void add(int u, int v, int c) {
		add_edge(u, v, c, 0);
		add_edge(v, u, 0, 0);
	}
	
	inline bool bfs() {
		for (int i = 1; i <= nt; ++i) {
			d[i] = -1;
			vis[i] = 0;
		}
		queue<int> q;
		q.push(S);
		vis[S] = 1;
		d[S] = 0;
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int i = hd[u]; i; i = edges[i].next) {
				edge &e = edges[i];
				if (!vis[e.to] && e.cap > e.flow) {
					vis[e.to] = 1;
					d[e.to] = d[u] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[T];
	}
	
	int dfs(int u, int a) {
		if (u == T || !a) {
			return a;
		}
		int flow = 0, f;
		for (int &i = cur[u]; i; i = edges[i].next) {
			edge &e = edges[i];
			if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
				e.flow += f;
				edges[i ^ 1].flow -= f;
				flow += f;
				a -= f;
				if (!a) {
					break;
				}
			}
		}
		return flow;
	}
	
	inline int solve() {
		int flow = 0;
		while (bfs()) {
			for (int i = 1; i <= nt; ++i) {
				cur[i] = hd[i];
			}
			flow += dfs(S, inf);
		}
		return flow;
	}
} solver;

void solve() {
	len = 1;
	for (int i = 0; i <= nt; ++i) {
		hd[i] = 0;
	}
	nt = 0;
	scanf("%d%d%d", &n, &m, &K);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &a[i].x, &a[i].y);
		id1[i] = id2[i] = 0;
		mk1[i] = mk2[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &b[i].x, &b[i].y);
		vis[i] = 0;
	}
	K = m - K;
	map< int, set<pii> > mp1, mp2;
	for (int i = 1; i <= n; ++i) {
		mp1[a[i].x].emplace(a[i].y, i);
		mp2[a[i].y].emplace(a[i].x, i);
	}
	S = ++nt;
	T = ++nt;
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		auto it = mp1[a[i].x].find(pii(a[i].y, i));
		if (next(it) != mp1[a[i].x].end()) {
			id1[i] = ++nt;
			++ans;
			solver.add(S, id1[i], 1);
		}
		it = mp2[a[i].y].find(pii(a[i].x, i));
		if (next(it) != mp2[a[i].y].end()) {
			id2[i] = ++nt;
			++ans;
			solver.add(id2[i], T, 1);
		}
	}
	for (int i = 1; i <= m; ++i) {
		e[i] = 0;
		c[i] = pii(0, 0);
		if (mp1.find(b[i].x) != mp1.end()) {
			auto it = mp1[b[i].x].lower_bound(pii(b[i].y, 0));
			if (it != mp1[b[i].x].end() && it != mp1[b[i].x].begin()) {
				c[i].fst = prev(it)->scd;
			}
		}
		if (mp2.find(b[i].y) != mp2.end()) {
			auto it = mp2[b[i].y].lower_bound(pii(b[i].x, 0));
			if (it != mp2[b[i].y].end() && it != mp2[b[i].y].begin()) {
				c[i].scd = prev(it)->scd;
			}
		}
		int x = c[i].fst, y = c[i].scd;
		if (x && y) {
			solver.add(id1[x], id2[y], 1);
			e[i] = len - 1;
		}
	}
	solver.solve();
	int cnt = K;
	for (int i = 1; i <= m; ++i) {
		if (!e[i]) {
			continue;
		}
		int j = e[i];
		if (edges[j].flow) {
			if (cnt) {
				--cnt;
				ans -= 2;
				vis[i] = 1;
				mk1[c[i].fst] = mk2[c[i].scd] = 1;
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (vis[i]) {
			continue;
		}
		if (cnt && ((c[i].fst && !mk1[c[i].fst]) || (c[i].scd && !mk2[c[i].scd]))) {
			--cnt;
			--ans;
			vis[i] = 1;
			if (c[i].fst) {
				mk1[c[i].fst] = 1;
			}
			if (c[i].scd) {
				mk2[c[i].scd] = 1;
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (!vis[i] && cnt) {
			--cnt;
			vis[i] = 1;
		}
	}
	printf("%d\n", ans);
	for (int i = 1; i <= m; ++i) {
		if (vis[i]) {
			continue;
		}
		printf("%d ", i);
	}
	putchar('\n');
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}