#pragma GCC target("avx512vl") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; #include using namespace atcoder; bitset<5064> dp[5000+1]; #pragma clang attribute push(__attribute__((target ("avx,avx2"))),apply_to=function) 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(); 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++; } for (int j = rcsum; j >= 0; j--) { dp[j+rcnt]|=(dp[j]<