#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

void solve() {
    int x,y,m;
    cin >> x >> y >> m;
    vector<pair<int, int>> uv(m);
    for(int i=0;i<m;++i){
        cin >> uv[i].first >> uv[i].second;
        --uv[i].first; --uv[i].second;
    }
    sort(uv.begin(), uv.end());
    uv.erase(unique(uv.begin(), uv.end()), uv.end());
    if(x<=y){
        cout << 0 << " " << y << endl << endl;
        for(int i=0;i<y;++i){
            cout << i+1 << " ";
        }
        cout << endl;
        return;
    }
    int m_=uv.size();
    vector<int> u(m_);
    vector<int> v(m_);
    vector<int> b_deg(x);
    vector<int> r_deg(y);
    for(int i=0;i<m_;++i){
        u[i]=uv[i].first;
        v[i]=uv[i].second;
        ++b_deg[u[i]];
        ++r_deg[v[i]];
    }
    int odd_stars=0;
    for(int i=0;i<x;++i){
        if(b_deg[i]%2>0){
            ++odd_stars;
        }
    }
    if((odd_stars+y)*2>=x+y){
        cout << odd_stars << " " << y << endl;
        for(int i=0;i<x;++i){
            if(b_deg[i]%2>0){
                cout << i+1 << " ";
            }
        }
        cout << endl;
        for(int i=0;i<y;++i){
            cout << i+1 << " ";
        }
        cout << endl;
        return;
    }
    vector<int> adj_even_stars(y);
    for(int i=0;i<m_;++i){
        if(b_deg[u[i]]%2==0){
            ++adj_even_stars[v[i]];
        }
    }
    int removed_star=0;
    for(int i=1;i<y;++i){
        if(adj_even_stars[i]*2-r_deg[i]>adj_even_stars[removed_star]*2-r_deg[removed_star]){
            removed_star=i;
        }
    }
    for(int i=0;i<m_;++i){
        if(v[i]==removed_star){
            if(b_deg[u[i]]%2>0){
                --odd_stars;
            } else {
                ++odd_stars;
            }
            --b_deg[u[i]];
        }
    }
    cout << odd_stars << " " << y-1 << endl;
    for(int i=0;i<x;++i){
        if(b_deg[i]%2>0){
            cout << i+1 << " ";
        }
    }
    cout << endl;
    for(int i=0;i<y;++i){
        if(i!=removed_star){
            cout << i+1 << " ";
        }
    }
    cout << endl;
}

int main(void) {
    int t;
    cin >> t;
    while(t--){
        solve();
        if(t>0){
            cout << endl;
        }
    }
    return 0;
}