Shrines setter solution

// Alei's submission
#include<bits/stdc++.h>
const bool TESTING=false;
using namespace std;
typedef long long int uli;
const int mxn=333;
int d[mxn][mxn];
map<pair<int,int>, pair<int,int> >mp;
vector<vector<int> >g;
vector<int>ans;
vector<int>holy;
int N, V, K, M, C, E;
int nqs=0;
pair<int,int>ask(int u,int v){
  if(mp.count({u,v}))return mp[{u,v}];
  nqs++;
  assert(nqs<=C);

  cout<<1<<" "<<u+1<<" "<<v+1<<endl;
//  cerr<<"nqs="<<nqs<<" C="<<C<<endl;
  int x,y;
  if(TESTING){
    x = 0, y = 0;
    for (int i = 0; i < K; i++){
      if (d[i][u] < d[i][v]) x++;
      if (d[i][v] < d[i][u]) y++;
    }
  }
  else{
    cin>>x>>y;
  }
  mp[{u,v}]={x,y};
  mp[{v,u}]={y,x};
//  cerr<<" ans="<<x<<";"<<y<<endl;
  return {x,y};
}
void answer(){
  cout<<2<<" "<<ans.size();
  sort(ans.begin(),ans.end());
  for(int x:ans)cout<<" "<<x+1;
  cout<<endl;

  if(TESTING){
    if(ans!=holy){
      cerr<<"wtf!"<<endl;
      cerr<<"ans=";for(int x:ans)cout<<x<<" ";cout<<endl;
      cerr<<"holy=";for(int x:holy)cout<<x<<" ";cout<<endl;
    }
    assert(ans==holy);
  }
}
void findDual(vector<set<int> >&adj){
  vector<vector<int> >cities;
  vector<pair<int,int> >petals;
  vector<vector<int> >contours;
  for(int i=0;i<N+N;i++){
    int j=(i+1)%(N+N);
    petals.push_back({i,j});
    contours.push_back({i,j});
  }
  while(true){
    if(petals.size()<=2){
      for(auto c:contours){
        cities.push_back(c);
      }
      break;
    }

    bool change=false;
    int sz=petals.size();
    /*
       for(int i=0;i<int(petals.size());i++){
       cerr<<"petal "<<petals[i].first<<";"<<petals[i].second<<": ";
       for(int x:contours[i])cerr<<x<<" ";cerr<<endl;
       }
       */
    for(int i=0;i<sz;i++){
      int j=(i+1)%sz;
      int u=petals[i].second;
      if(adj[u].empty()){
        pair<int,int>petal={petals[i].first,petals[j].second};
        auto contour=contours[i];
        assert(contours[j][0]==u);
        for(int x:contours[j])if(x!=u)contour.push_back(x);
        petals.erase(petals.begin()+i);
        contours.erase(contours.begin()+i);

        petals[i%petals.size()]=petal;
        contours[i%petals.size()]=contour;
        change=true;
        break;
      }
    }
    if(change)continue;
    for(int i=0;i<sz;i++){
      int u=petals[i].first;
      int v=petals[i].second;
      if(adj[u].count(v)){
        adj[u].erase(v);
        adj[v].erase(u);
        cities.push_back(contours[i]);

        contours[i]={u,v};
        change=true;
        break;
      }
    }
    if(change)continue;

    int u,v,w=-1;
    int at=-1;

    for(int i=0;i<sz && w==-1;i++){
      u=petals[i].first;
      v=petals[i].second;
      for(int x:adj[u]){
        if(adj[v].count(x)){
          w=x;
          at=i;
          break;
        }
      }
    }
    assert(w!=-1);
    auto city=contours[at];
    city.push_back(w);
    cities.push_back(city);

    assert(w!=-1);
    int lft=(at-1+sz)%sz;
    int rht=(at+1)%sz;
    int z=petals[lft].second;
    adj[z].erase(w);
    adj[w].erase(z);

    petals[at]={z,w};
    contours[at]={z,w};

    z=petals[rht].first;
    adj[z].erase(w);
    adj[w].erase(z);

    petals.insert(petals.begin()+at+1,{w,z});
    contours.insert(contours.begin()+at+1,{w,z});
  }
  sort(cities.begin(),cities.end());
/*
  cerr<<"cities"<<endl;
  for(auto c:cities){
    for(int x:c)cerr<<x+1<<" ";cerr<<endl;
  }
*/

  int c=cities.size();
  vector<int>o(c);
  iota(o.begin(),o.end(),0);
  vector<vector<int>>sorted;

  for(vector<int>c : cities){
    sort(c.begin(),c.end());
    for(int i=1;i<int(c.size());i++)assert(c[i]>c[i-1]);
    sorted.push_back(c);
  }
  sort(o.begin(),o.end(),[&sorted](int i,int j)->bool{
      return sorted[i]<sorted[j];
      });
  vector<int>index(c);
  for(int i=0;i<c;i++){
    index[o[i]]=i;
  }
  map<pair<int,int>,set<int> >mapa;
  for(int it=0;it<c;it++){
    auto c=cities[it];
    int cnt=c.size();
    for(int i=0;i<cnt;i++){
      int u=c[i];
      int v=c[(i+1)%cnt];
      if(u>v)swap(u,v);
      mapa[{u,v}].insert(index[it]);
    }
  }
  g.clear();
  g.resize(c);
  for(auto p:mapa){
    assert(p.second.size()<=2);
    if(p.second.size()==2){
      int u=*p.second.begin();
      int v=*p.second.rbegin();
      g[u].push_back(v);
      g[v].push_back(u);
    }
  }
  C=c;
  assert(c<=300);
  assert(2<=K && K<=C);
}

void pre(){
  assert(int(g.size())==C);
  vector<vector<int> >h(C);
  for(int i=0;i<E;i++){
    int u,v;
    cin>>u>>v;
    h[--u].push_back(--v);
    h[v].push_back(u);
  }
  for(int i=0;i<C;i++){
    sort(g[i].begin(),g[i].end());
    sort(h[i].begin(),h[i].end());
    assert(g[i]==h[i]);
  }
  assert(g==h);
  //bfs from gods home
  for (int i = 0; i < K; i++){
    int u;
    cin>>u;
    assert(1<=u&&u<=C);
    --u;
    for (int j = 0; j < C; j++) d[i][j] = -1;
    d[i][u] = 0;
    queue <int> q;
    q.push(u);
    while (!q.empty()){
      u = q.front();
      q.pop();
      for (int v : g[u]){
        if (d[i][v] == -1){
          d[i][v] = d[i][u] + 1;
          q.push(v);
        }
        else assert(d[i][v]<=d[i][u]+1);
      }
    }

    for (int j = 0; j < C; j++) assert(d[i][j]>=0);
  }
  //find holy cities
  int mini = 1e9;
  holy.clear();
  for (int u = 0; u < C; u++){
    int sm = 0;
    for (int i = 0; i < K; i++){
      sm += d[i][u];
    }
    if (sm == mini){
      holy.push_back(u);
    }
    else if(sm < mini){
      mini = sm;
      holy = {u};
    }
  }
  assert(mini<1e9);
  sort(holy.begin(),holy.end());
}
int main(){
  int t;
  cin>>t;
  int sm=0;
  for(int tt=0;tt<t;tt++){
    cin>>N>>V>>M>>K;
//    assert(K==2);
    if(TESTING)cin>>C>>E;

    vector<set<int> >adj(V);
    for(int i=0;i<M;i++){
      int u,v;
      cin>>u>>v;
      assert(1<=u&&u<=V);
      assert(1<=v&&v<=V);
      adj[--u].insert(--v);
      adj[v].insert(u);
    }
    findDual(adj);
    sm+=C;
    assert(sm<=1e4);
    if(TESTING)pre();
    mp.clear();
    nqs=0;
    int u=0;
    vector<bool>vis(C);
    vector<int>parent(C,-1);
    vis[u]=true;
    parent[u]=u;
    int old=-1;
    while(old!=u){
      old=u;
      for(int v:g[u]){
        if(!vis[v]){
          auto p=ask(v,u);
          int x=p.first;

          if(x+x>=K){
            vis[v]=true;
            parent[v]=u;
            u=v;
            break;
          }
        }
      }
    }
    queue<int>q;
    q.push(u);
    fill(vis.begin(),vis.end(),false);
    vis[u]=true;
    ans.clear();
    ans.push_back(u);

    while(u!=parent[u]){
      auto qry=ask(parent[u],u);
      int x=qry.first;
      u=parent[u];
      if(x+x>=K){
        q.push(u);
        vis[u]=true;
        ans.push_back(u);
      }
      else break;
    }
    u=q.front();
    while(u!=parent[u]){
      u=parent[u];
      vis[u]=true;
    }

    while(!q.empty()){
      u=q.front();
      q.pop();
      for(int v:g[u]){
        if(vis[v])continue;
        vis[v]=true;
        auto p=ask(v,u);
        int x=p.first;
        if(x+x>=K){
          vis[v]=true;
          ans.push_back(v);
          q.push(v);
        }
      }
    }
    answer();
  }
  return 0;
}