题解 舞动的夜晚

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 200010
#define ll long long
//#define int long long

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n, m, t, lim;
int cnt[N], head[N], size;
struct edge{int from, to, next;}e[N<<1];
inline void add(int s, int t) {e[++size].to=t; e[size].from=s; e[size].next=head[s]; head[s]=size;}

// 这个暴力是假的，暴力应该用最大流跑
namespace force{
	int deg[N];
	bool del[N], ans2[N], vis[N];
	int check(int s) {
		// cout<<"check: "<<s<<endl;
		for (int i=1; i<=lim; ++i) deg[i]=cnt[i];
		memset(vis, 0, sizeof(bool)*(lim+10));
		int ans=0;
		queue<int> q;
		if (~s) {
			// cout<<"del: "<<e[s].from<<' '<<e[s].to<<endl;
			vis[e[s].from]=vis[e[s].to]=1;
			++ans;
			q.push(e[s].from); q.push(e[s].to);
		}
		for (int i=1; i<=lim; ++i) if (deg[i]==1 && !vis[i]) q.push(i);
		while (q.size()) {
			int u=q.front(); q.pop();
			// cout<<"u: "<<u<<endl;
			if (vis[u]) {
				for (int i=head[u],v; ~i; i=e[i].next) {
					v = e[i].to;
					if (!vis[v] && --deg[v]==1) q.push(v);
				}
				continue;
			}
			for (int i=head[u],v; ~i; i=e[i].next) {
				v = e[i].to;
				if (vis[v]) continue;
				if (vis[u]) {if (--deg[v]==1) q.push(v);}
				else {
					vis[u]=vis[v]=1; q.push(v);
					++ans;
				}
			}
		}
		// cout<<"ans: "<<ans<<endl;
		// cout<<"vis: "; for (int i=1; i<=lim; ++i) cout<<vis[i]<<' '; cout<<endl;
		// cout<<"deg: "; for (int i=1; i<=lim; ++i) cout<<deg[i]<<' '; cout<<endl;
		int dlt=0;
		for (int i=1; i<=lim; ++i) if (!vis[i] && deg[i]) ++dlt;
		return ans+dlt/2;
	}
	void solve() {
		memset(head, -1, sizeof(head));
		for (int i=1,u,v; i<=t; ++i) {
			u=read(); v=read()+n;
			add(u, v); add(v, u);
			++cnt[u], ++cnt[v];
		}
		int ans=0, maxn=check(-1);
		// cout<<"maxn: "<<maxn<<endl;
		for (int i=1; i<=t; ++i) {
			// del[i]=1;
			if (check(i*2)<maxn) ++ans, ans2[i]=1;
			// del[i]=0;
		}
		printf("%d\n", ans);
		for (int i=1; i<=t; ++i) if (ans2[i]) printf("%d ", i); printf("\n");
	}
}

namespace task{
	int head[N], size=1, dep[N], cur[N], S, T, scnt, dfn[N], low[N], bel[N], sta[N], top, tot;
	bool vis[N<<1], vis2[N];
	struct edge{int from, to, next,val;}e[N<<1];
	inline void add(int s, int t, int w) {e[++size].to=t; e[size].from=s; e[size].val=w; e[size].next=head[s]; head[s]=size;}
	bool bfs(int s, int t) {
		memset(dep, 0, sizeof(dep));
		queue<int> q;
		dep[s]=1;
		cur[s]=head[s];
		q.push(s);
		int u;
		while (q.size()) {
			u=q.front(); q.pop();
			// cout<<"u: "<<u<<endl;
			for (int i=head[u],v; ~i; i=e[i].next) {
				v = e[i].to;
				// cout<<"v: "<<v<<' '<<e[i].val<<' '<<dep[v]<<endl;
				if (e[i].val && !dep[v]) {
					dep[v]=dep[u]+1;
					cur[v]=head[v];
					if (v==t) return 1;
					q.push(v);
				}
			}
		}
		return 0;
	}
	int dfs(int u, int in) {
		if (u==T || !in) return in;
		int rest=in;
		for (int i=cur[u],v; ~i; cur[u]=i=e[i].next) {
			v = e[i].to;
			if (e[i].val && dep[v]==dep[u]+1) {
				int tem=dfs(v, min(e[i].val, in));
				if (!tem) dep[v]=0;
				else {
					e[i].val-=tem;
					e[i^1].val+=tem;
					rest-=tem;
				}
				if (!rest) break;
			}
		}
		return in-rest;
	}
	void tarjan(int u) {
		// cout<<"tarjan: "<<u<<endl;
		dfn[u]=low[u]=++tot;
		sta[++top]=u; vis2[u]=1;
		for (int i=head[u],v; ~i; i=e[i].next) if (e[i].val) {
			v = e[i].to;
			// cout<<"v: "<<v<<endl;
			if (!dfn[v]) {
				tarjan(v);
				low[u]=min(low[u], low[v]);
			}
			else if (vis2[v]) low[u]=min(low[u], dfn[v]);
		}
		if (dfn[u]==low[u]) {
			++scnt;
			do {
				// cout<<"top: "<<sta[top]<<endl;
				bel[sta[top]]=scnt; vis2[sta[top--]]=0;
				// cout<<"top2: "<<top<<endl;
			} while (sta[top+1]!=u);
		}
	}
	void solve() {
		memset(head, -1, sizeof(head));
		S=lim+1, T=lim+2;
		for (int i=1,u,v; i<=t; ++i) {
			u=read(); v=read()+n;
			add(u, v, 1); add(v, u, 0);
		}
		for (int i=1; i<=n; ++i) add(S, i, 1), add(i, S, 0);
		for (int i=1; i<=m; ++i) add(n+i, T, 1), add(T, n+i, 0);
		int tem=0;
		while (bfs(S, T)) tem+=dfs(S, INF);
		// cout<<"eval: "<<endl; for (int i=2; i<=size; ++i) cout<<"e: "<<e[i].from<<' '<<e[i].to<<' '<<e[i].val<<endl;
		// cout<<"tem: "<<tem<<endl;
		for (int i=1; i<=lim+2; ++i) if (!dfn[i]) tarjan(i);
		// cout<<"scnt: "<<scnt<<endl;
		// cout<<"bel: "; for (int i=1; i<=lim; ++i) cout<<bel[i]<<' '; cout<<endl;
		int ans=0;
		for (int i=2; i<=t*2; i+=2) if (e[i].val && bel[e[i].from]!=bel[e[i].to]) vis[i]=1, ++ans;
		printf("%d\n", ans);
		for (int i=2; i<=t*2; i+=2) if (vis[i]) printf("%d ", i/2); printf("\n");
	}
}

signed main()
{
	freopen("night.in", "r", stdin);
	freopen("night.out", "w", stdout);

	n=read(); m=read(); t=read(); lim=n+m;
	// force::solve();
	task::solve();

	return 0;
}