/*
  Max flow (Ford-Fulkerson's algorithm)

  
 */
// cygwin はlrand48()が腐ってるのでrandom_shuffleが動かない
// 回避策
#undef _GLIBCPP_HAVE_DRAND48
#include<algorithm>

#include<iostream>
#include<fstream>
#include<iterator>
#include<map>
#include<set>
#include<vector>
#include<deque>

#include<ctime>
#include<cstdlib>

#include<ext/numeric>
#include<sstream>
#include<functional>

#define DEBUG_
#undef DEBUG_

using namespace std;
using namespace __gnu_cxx;

typedef pair<int, int> point;
typedef int weight;

const weight infty__ = 9999999;

#ifdef DEBUG_
ostream& operator <<(ostream &os, const point &p)
{
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
#endif

struct edge{
  point dest;
  weight cap;
  // 自分のフローと、逆方向の辺のフロー
  weight *pflow;
  weight *preverseflow;
  
  edge(){};
  edge(point dest, weight cap, weight* pflow, weight *preverseflow)
       :dest(dest), cap(cap), pflow(pflow), preverseflow(preverseflow){};

  weight flow(){return *pflow - *preverseflow;};
  weight residue(){return cap - flow();};
  void increase(weight w){
    // まず逆方向を減らす
    *preverseflow -= w;
    if(*preverseflow < 0){
      // += - 打ち間違えやすいので注意
      *pflow += -*preverseflow;
      *preverseflow = 0;
    }
  };
};

typedef vector<edge> edges;
typedef map<point, edges> graph;
typedef vector<edge*> path;

void makeEdgeOneWay(graph &g, point src, point dest, weight cap)
{
  // 単方向の辺はcap = 0として表現
  weight *pflow = new weight(0);
  weight *pnoflow = new weight(0);
  g[src ].push_back(edge(dest, cap, pflow, pnoflow));
  g[dest].push_back(edge(src,  0, pnoflow, pflow));
}

weight augment(graph &g, path& p)
{
  if(p.size() < 1) return 0;

  // tauは「最大流せる量」
  weight tau = infty__;
  for(int i = 0; i < p.size(); i++){
    edge* pe = p[i];
    tau = min(tau, pe -> residue());
  }

  // その分増やす
  for(int i = 0; i < p.size(); i++){
    edge *pe = p[i];
    pe -> increase(tau);
  }
  return tau;
}

weight maxflow(graph &g, point st, point en)
{
  if(g[st].size() == 0)return 0;

  // 増加パスがある限りBFS
  weight totalFlow = 0;
  bool pathFound;
  do{
    // pathを生成。BFSで、全点を最大一回走査する。
    // このとき、残余フローが0でない辺のみを選んでBFSすると
    // 増大路が存在
    set<point> visited;
    visited.insert(st);

    pathFound = false;
    deque<path> toBeProcessed;
    toBeProcessed.push_back(path());

    while(!toBeProcessed.empty()){
      path p = toBeProcessed.front();
      toBeProcessed.pop_front();

      point currentPoint = st;
      if(!p.empty()){
        currentPoint = p.back() -> dest;
        if(currentPoint == en){
          // ルートができるたびに拡張
          totalFlow += augment(g, p);
          pathFound = true;
          break;
        }
      }

      edges& es = g[currentPoint];
      // 辺の順序を適当に並び替える -- capが無理数の場合の無限ループ防止
      vector<int> shuffledIndex(es.size());
      iota(shuffledIndex.begin(), shuffledIndex.end(), 0);
      random_shuffle(shuffledIndex.begin(), shuffledIndex.end());

      for(int i = 0; i < es.size(); i++){
        int ix = shuffledIndex[i]; // capが整数なら上を消してここをix = iとしてよい、但し変なデータに脆弱
        // すでに通った辺は除外
        if(visited.count(es[ix].dest)) continue;
        // cap - flow = 0も除外
        if(es[ix].residue() == 0) continue;

        // 新たな点を追加
        path newpath(p);
        newpath.push_back(&es[ix]);
        visited.insert(es[ix].dest);
        // BFSの駆動
        toBeProcessed.push_back(newpath);
      }
    }
  }while(pathFound);
  return totalFlow;
}

/*
  ACM/ICPC Japan practice contest for World Finals
  Spring camp - problem A
  Bring Them There (NorthEast
 */

int main(void)
{
  ifstream cin("bring.in");
  int Ncases;
  cin >> Ncases;
  while(Ncases--){
    graph g;
    int N, M, K, S, T;
    cin >> N >> M >> K >> S >> T;

    int MaxDay = K + N + 1;
    for(int i = 0; i < M; i++){
      int src, dest;
      cin >> src >> dest;
      for(int j = 0; j < MaxDay - 1; j++){
        makeEdgeOneWay(g,
                       make_pair(src, j),
                       make_pair(dest, j + 1), 1);
        makeEdgeOneWay(g,
                       make_pair(dest, j),
                       make_pair(src, j + 1), 1);
      }
    }
    for(int i = 1; i <= N; i++){
      for(int j = 0; j < MaxDay - 1; j++){
        makeEdgeOneWay(g,
                       make_pair(i, j),
                       make_pair(i, j + 1), K);
      }
    }
//    cout << "calc: " << endl;

    for(int i = 1; i < MaxDay; i++){
      for(graph::iterator git = g.begin();
          git != g.end();
          git++){
        edges &es = git -> second;
        for(int j = 0; j < es.size(); j++){
          *(es[j].pflow) = 0;
        }
      }
      int totalflow = maxflow(g, make_pair(S, 0), make_pair(T, i));
//      cout << "Day" << i << ": " << totalflow << endl;
      if(totalflow >= K){
#ifdef DEBUG_
        for(graph::iterator git = g.begin();
            git != g.end(); git++){
          edges &es = git -> second;
          for(int i = 0; i < es.size(); i++){
            if(*(es[i].pflow) != 0)
              cout << git->first << "->" << es[i].dest << ": " << *(es[i].pflow) << endl;
          }
        }
        cout << endl;
#endif
        cout << i << endl;
        vector<int> current_point(K+1, S);
        current_point[0] = -1;
        for(int j = 0; j < i; j++){
          // 流量1のflowに分割する
          vector<pair<int, int> > moves;
          for(int k = 1; k <= N; k++){
            edges &es = g[make_pair(k, j)];
            for(int l = 0; l < es.size();){
              if(*(es[l].pflow)){
                (*(es[l].pflow)) --;
                moves.push_back(make_pair(k, es[l].dest.first));
//                cout << "adding: " << k << "->" << es[l].dest.first << endl;
              }else{
                l++;
              }
            }
          }
          for(int k = 0; k < moves.size(); k++){
            for(int l = k + 1; l < moves.size(); l++){
              if(moves[k].first == moves[l].second &&
                 moves[k].second == moves[l].first){
                moves[k].second = moves[k].first;
                moves[l].second = moves[l].first;
              }
            }
          }
          vector<int> new_point(current_point);
          ostringstream os;
          int nline = 0;
          for(int k = 1; k <= K; k++){
            for(int l = 0; l < moves.size(); l++){
              if(moves[l].first == current_point[k]){
                current_point[k] = -1;
                new_point[k] = moves[l].second;
                if(moves[l].first != moves[l].second){
                  os << "  " << k << " " << moves[l].second;
                  nline ++;
                }
                moves.erase(moves.begin() + l);
                break;
              }
            }
          }
          cout << nline << os.str();
          current_point = new_point;
          cout << endl;
        }
        if(Ncases != 1)
          cout << endl;
        break;
      }
    }
  }
  return 0;
}