#include using namespace std; #include using namespace atcoder; int main() { int H, W, N; cin >> H >> W >> N; atcoder::dsu d(H+W); for (int i = 0; i < N; i++) { int a, b; cin >> a >> b; a--; b--; d.merge(a, b+H); } vector> G = d.groups(); int K = (int)G.size(); bitset<2001> dp[H+1]; dp[0][0] = 1; int rcsum = 0; for (int i = 0; i < K; i++) { vector g = G[i]; int rcnt = 0, ccnt = 0; for (int v : g) { if (v < H) rcnt++; else ccnt++; } rcsum += rcnt; for (int j = rcsum; j >= 0; j--) { dp[j+rcnt]|=(dp[j]<