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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e3+7;
vector<int>V[LIM], musza;
pair<int,int>P[LIM];
int odw[LIM], odw2[LIM], deg[LIM], stos[LIM], n, m, k, mi, aktm, aktn, akt_stos;
int moze[LIM], ktore[LIM], akt_ktore;
void rek(int x, int l) {
  if(x>k) return;
  while(l<m && (odw[P[l].st] || odw[P[l].nd] || deg[P[l].st]<=1 || deg[P[l].nd]<=1)) ++l;
  if(l<m) {
    int i=l;
    int z=0;
    for(auto j : V[P[i].st]) if(!odw[j]) {
      odw[j]=1; ++z;
      stos[akt_stos++]=j;
      for(auto p : V[j]) --deg[p];
    }
    rek(x+z, l+1);
    while(z--) {
      int j=stos[--akt_stos];
      odw[j]=0;
      for(auto p : V[j]) ++deg[p];
    }
    z=0;
    for(auto j : V[P[i].nd]) if(!odw[j]) {
      odw[j]=1; ++z;
      stos[akt_stos++]=j;
      for(auto p : V[j]) --deg[p];
    }
    rek(x+z, l+1);
    while(z--) {
      int j=stos[--akt_stos];
      odw[j]=0;
      for(auto p : V[j]) ++deg[p];
    }
    if(deg[P[i].st]>2 || deg[P[i].nd]>2) {
      odw[P[i].st]=odw[P[i].nd]=1;
      stos[akt_stos++]=P[i].st;
      stos[akt_stos++]=P[i].nd;
      for(auto p : V[P[i].st]) --deg[p];
      for(auto p : V[P[i].nd]) --deg[p];
      rek(x+2, l+1);
      for(auto p : V[P[i].st]) ++deg[p];
      for(auto p : V[P[i].nd]) ++deg[p];
      akt_stos-=2;
      odw[P[i].st]=odw[P[i].nd]=0;
      return;
    }
  }
  rep(i, m) if(!odw[P[i].st] && !odw[P[i].nd]) {
    if(deg[P[i].st]>1) {
      if(!odw2[P[i].st]) ++x;
      odw2[P[i].st]=1;
    } else if(deg[P[i].nd]>1) {
      if(!odw2[P[i].nd]) ++x;
      odw2[P[i].nd]=1;
    } else {
      odw2[P[i].st]=odw2[P[i].nd]=1;
      ++x;
    }
  }
  if(x>k) {
    rep(i, m) odw2[P[i].st]=odw2[P[i].nd]=0;
    return;
  }
  if(x<k) {
    mi=k=x;
    rep(i, akt_ktore) moze[ktore[i]]=0;
    akt_ktore=0;
  }
  rep(i, akt_stos) if(!moze[stos[i]]) {
    moze[stos[i]]=1;
    ktore[akt_ktore++]=stos[i];
  }
  mi=min(mi, k);
  rep(i, m) {
    if(odw2[P[i].st] && !moze[P[i].st]) {
      moze[P[i].st]=1;
      ktore[akt_ktore++]=P[i].st;
    }
    if(odw2[P[i].nd] && !moze[P[i].nd]) {
      moze[P[i].nd]=1;
      ktore[akt_ktore++]=P[i].nd;
    }
  }
  rep(i, m) odw2[P[i].st]=odw2[P[i].nd]=0;
}
void solve() {
  aktm=aktn=akt_stos=akt_ktore=0;
  musza.clear();
  cin >> n >> m >> k;
  rep(i, n) {
    odw[i]=odw2[i]=deg[i]=stos[i]=moze[i]=ktore[i]=0;
    V[i].clear();
  }
  rep(i, m) {
    cin >> P[i].st >> P[i].nd;
    --P[i].st; --P[i].nd;
  }
  sort(P, P+m);
  vector<pair<int,int>>tmp;
  tmp.pb(P[0]);
  for(int i=1; i<m; ++i) if(P[i]!=P[i-1]) tmp.pb(P[i]);
  rep(i, tmp.size()) P[i]=tmp[i];
  m=tmp.size();
  rep(i, m) {
    if(rand()%2) swap(P[i].st, P[i].nd);
    ++deg[P[i].st];
    ++deg[P[i].nd];
  }
  rep(i, m) swap(P[i], P[rand()%(i+1)]);
  while(k>1) {
    pair<int,int>ma={-1, -1};
    rep(i, n) ma=max(ma, {deg[i], i});
    if(ma.st>k) --k;
    else break;
    musza.pb(ma.nd);
    rep(i, m) if(P[i].st==ma.nd || P[i].nd==ma.nd) {
      --deg[P[i].st];
      --deg[P[i].nd];
      P[i]={-1, -1};
    }
  }
  rep(i, m) if(P[i].st!=-1) P[aktm++]=P[i];
  m=aktm;
  rep(i, n) if(deg[i]) ++aktn;
  rep(i, m) {
    V[P[i].st].pb(P[i].nd);
    V[P[i].nd].pb(P[i].st);
  }
  mi=k+1;
  rek(0, 0);
  if(mi>k) {
    cout << -1 << '\n';
    return;
  }
  cout << musza.size()+mi << " " << musza.size()+akt_ktore << '\n';
  rep(i, akt_ktore) musza.pb(ktore[i]);
  sort(all(musza));
  for(auto i : musza) cout << i+1 << " ";
  cout << '\n';
}
int main() {
  srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  ios_base::sync_with_stdio(0); cin.tie(0);
  int _;
  cin >> _;
  while(_--) solve();
}