#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <math.h>
#include <queue>
#include <map>
#include <cstring>
#include <assert.h>
#include <random>
using namespace std;
typedef long long ll;
void solve() {
  int n, m , k;
  cin >> n >> m >> k;
  vector<vector<int>> e(n + 1);
  vector<int> deg(n + 1), del(n + 1);
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }
  queue<int> q;
  for (int i = 1; i <= n;i++) {
    if (deg[i] <= 2 * k) {
      q.push(i);
      del[i] = 1 ;
    }
  }
  while(q.size()) {
    int u = q.front();
    q.pop();
    assert(deg[u] <= 2 * k) ;
    for (int v : e[u]) {
      if (del[v]) continue;
      deg[v]--;
      if (deg[v] <= 2 * k) {
        q.push(v);
        del[v] = 1 ;
      }
    }
  }
  // cout << "!" << endl;
  vector<int> cnt(n + 1), group(n + 1);
  while(1) {
    int flag = 0;
    for (int i = 1; i <= n; i++) {
      if (del[i]) continue;
      if (cnt[i] <= k) {
        flag = 1;
        for (auto v : e[i]) {
          if (del[v]) continue;
          if (group[v] == group[i]) cnt[v]++;
          else {
            cnt[v]--;
          }
        }
        group[i] = 1 - group[i];
        cnt[i] = deg[i] - cnt[i];
      }
    }
    if (!flag) break;
  }
  vector<int> ans1, ans2;
  for (int i = 1; i <= n; i++) {
    if (del[i]) continue;
    if (group[i]) ans1.push_back(i);
    else ans2.push_back(i);
  }
  assert(ans1.size()>=k+1 and ans2.size()>=k+1);
  cout << ans1.size() << " ";
  for (int i = 0; i < ans1.size(); i++) {
    cout << ans1[i] << " ";
  }
  cout << "\n";
  cout << ans2.size() << " ";
  for (int i = 0; i < ans2.size(); i++) {
    cout << ans2[i] << " ";
  }
  cout << "\n";
}
int main() {
  #ifdef _DEBUG
    freopen("data.txt", "r", stdin);
  #endif
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while(T--) solve(); 
}