1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#else
#define debug(x) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mem(v,x) memset(v,x,sizeof v)

using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-5;
constexpr ll N = 2025, INF = 1e18, MOD = 998244353, K = 11, inf = 1e9;
constexpr ll modpow(ll e,ll p,ll m=MOD) {ll r=1; for(;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r;}
constexpr inline ll cdiv(ll x, ll m) { return (x+m-1)/m; } // ceiling divide, x/m for flooring divide

struct BipartiteMatching {
    vector<int> G[N];
    int mx[N],my[N],vis[N],now,n;
    void init(int _n) {
        n = _n;
        for(int i = 1; i <= n; i++) G[i].clear();
    }
    void addEdge(int x,int y) {
        G[x].pb(y);
    }
    bool dfs(int x) {
        if(vis[x] == now) return false;
        vis[x] = now;
        for(int y:G[x]) if(my[y]==-1 || dfs(my[y])) return my[mx[x]=y]=x, true;
        return false;
    }
    int solve() {
        int ans = 0;
        for(int i = 1; i <= n; i++) vis[i] = 0, mx[i] = -1, my[i] = -1;
        for(int i = 1; i <= n; i++) if(mx[i] == -1) for(int j:G[i]) if(my[j]==-1) {
            my[mx[i]=j]=i;
            ans++;
            break;
        }
        for(now = 1; now <= n; now++) if(mx[now] == -1 && dfs(now)) ans++;
        return ans;
    }
} sv;
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int p,q,m;
        cin >> p >> q >> m;
        if(max(p,q) < N) {
            sv.init(max(p,q));
            for(int i = 0; i < m; i++) {
                int a,b;
                cin >> a >> b;
                sv.addEdge(a,b);
            }
            cout << sv.solve() << '\n';
        }else {
            vector<vector<int>> tr(p+q+1);
            vector<array<int,2>> dp(p+q+1);
            //assert(m == p+q-1);
            for(int i = 0; i < m; i++) {
                int a,b;
                cin >> a >> b;
                tr[a].pb(b+p);
                tr[b+p].pb(a);
            }
            function<void(int,int)> dfs = [&](int i, int p) {
                dp[i][1] = (p != 0);
                int mx = 0;
                for(int j:tr[i]) if(j!=p) {
                    dfs(j,i);
                    dp[i][1] += dp[j][0];
                    dp[i][0] += dp[j][0];
                    mx = max(mx, dp[j][1] - dp[j][0]);
                }
                dp[i][0] += mx;
            };
            dfs(1,0);
            cout << max(dp[1][0],dp[1][1]) << '\n';
        }
    }
}