// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #define INTERACTIVE

#include <bits/stdc++.h>
using namespace std;

namespace templates {
// type
using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on

// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on

// const value
const ll MOD1   = 1000000007;
const ll MOD9   = 998244353;
const double PI = acos(-1);

// other macro
#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)

// function
vector<char> stoc(string &S) {
    int n = S.size();
    vector<char> ret(n);
    for (int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}
string ctos(vector<char> &S) {
    int n      = S.size();
    string ret = "";
    for (int i = 0; i < n; i++) ret += S[i];
    return ret;
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
    return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
    auto b = clamp(a, l, r);
    return (a != b ? a = b, 1 : 0);
}

template <typename T>
T sum(vector<T> &A) {
    T tot = 0;
    for (auto a : A) tot += a;
    return tot;
}

template <typename T>
vector<T> compression(vector<T> X) {
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    return X;
}

// input and output
namespace io {
// __int128_t
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << ' ';
    }
    return os;
}

// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
    is >> A.first >> A.second;
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
    os << A.first << ' ' << A.second;
    return os;
}

// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        is >> A[i];
    }
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// tuple
template <typename T, size_t N>
struct TuplePrint {
    static ostream &print(ostream &os, const T &t) {
        TuplePrint<T, N - 1>::print(os, t);
        os << ' ' << get<N - 1>(t);
        return os;
    }
};
template <typename T>
struct TuplePrint<T, 1> {
    static ostream &print(ostream &os, const T &t) {
        os << get<0>(t);
        return os;
    }
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
    return os;
}

// io functions
void FLUSH() {
    cout << flush;
}

void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(std::forward<Tail>(tail)...);
}

template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << sep;
    }
    cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
    cout << A << end;
}
template <typename T>
void prispa(T A) {
    priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
    if (f)
        print(A);
    else
        print(B);
    return f;
}

template <class... T>
void inp(T &...a) {
    (cin >> ... >> a);
}

} // namespace io
using namespace io;

// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<int>> edges(n, vector<int>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        u -= indexed;
        v -= indexed;
        edges[u].push_back(v);
        if (!direct) edges[v].push_back(u);
    }
    return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
    return read_edges(n, n - 1, false, indexed);
}

template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        T w;
        inp(w);
        u -= indexed;
        v -= indexed;
        edges[u].push_back({v, w});
        if (!direct) edges[v].push_back({u, w});
    }
    return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
    return read_wedges<T>(n, n - 1, false, indexed);
}

// yes / no
namespace yesno {

// yes
inline bool yes(bool f = true) {
    cout << (f ? "yes" : "no") << endl;
    return f;
}
inline bool Yes(bool f = true) {
    cout << (f ? "Yes" : "No") << endl;
    return f;
}
inline bool YES(bool f = true) {
    cout << (f ? "YES" : "NO") << endl;
    return f;
}

// no
inline bool no(bool f = true) {
    cout << (!f ? "yes" : "no") << endl;
    return f;
}
inline bool No(bool f = true) {
    cout << (!f ? "Yes" : "No") << endl;
    return f;
}
inline bool NO(bool f = true) {
    cout << (!f ? "YES" : "NO") << endl;
    return f;
}

// possible
inline bool possible(bool f = true) {
    cout << (f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Possible(bool f = true) {
    cout << (f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool POSSIBLE(bool f = true) {
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// impossible
inline bool impossible(bool f = true) {
    cout << (!f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Impossible(bool f = true) {
    cout << (!f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool IMPOSSIBLE(bool f = true) {
    cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// Alice Bob
inline bool Alice(bool f = true) {
    cout << (f ? "Alice" : "Bob") << endl;
    return f;
}
inline bool Bob(bool f = true) {
    cout << (f ? "Bob" : "Alice") << endl;
    return f;
}

// Takahashi Aoki
inline bool Takahashi(bool f = true) {
    cout << (f ? "Takahashi" : "Aoki") << endl;
    return f;
}
inline bool Aoki(bool f = true) {
    cout << (f ? "Aoki" : "Takahashi") << endl;
    return f;
}

} // namespace yesno
using namespace yesno;

} // namespace templates
using namespace templates;

////////// https://codeforces.com/blog/entry/90513

namespace hamil {
template <typename T>
bool chkmax(T &x, T y) {
    return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T &x, T y) {
    return x > y ? x = y, true : false;
}
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
#define ll long long
namespace LCT {
vector<vi> ch;
vi fa, rev;
void init(int n) {
    ch.resize(n + 1);
    fa.resize(n + 1);
    rev.resize(n + 1);
    for (int i = 0; i <= n; i++) ch[i].resize(2), ch[i][0] = ch[i][1] = fa[i] = rev[i] = 0;
}
bool isr(int a) {
    return !(ch[fa[a]][0] == a || ch[fa[a]][1] == a);
}
void pushdown(int a) {
    if (rev[a]) {
        rev[ch[a][0]] ^= 1, rev[ch[a][1]] ^= 1;
        swap(ch[a][0], ch[a][1]);
        rev[a] = 0;
    }
}
void push(int a) {
    if (!isr(a)) push(fa[a]);
    pushdown(a);
}
void rotate(int a) {
    int f = fa[a], gf = fa[f];
    int tp  = ch[f][1] == a;
    int son = ch[a][tp ^ 1];
    if (!isr(f)) ch[gf][ch[gf][1] == f] = a;
    fa[a] = gf;

    ch[f][tp] = son;
    if (son) fa[son] = f;

    ch[a][tp ^ 1] = f, fa[f] = a;
}
void splay(int a) {
    push(a);
    while (!isr(a)) {
        int f = fa[a], gf = fa[f];
        if (isr(f))
            rotate(a);
        else {
            int t1 = ch[gf][1] == f, t2 = ch[f][1] == a;
            if (t1 == t2)
                rotate(f), rotate(a);
            else
                rotate(a), rotate(a);
        }
    }
}
void access(int a) {
    int pr = a;
    splay(a);
    ch[a][1] = 0;
    while (1) {
        if (!fa[a]) break;
        int u = fa[a];
        splay(u);
        ch[u][1] = a;
        a        = u;
    }
    splay(pr);
}
void makeroot(int a) {
    access(a);
    rev[a] ^= 1;
}
void link(int a, int b) {
    makeroot(a);
    fa[a] = b;
}
void cut(int a, int b) {
    makeroot(a);
    access(b);
    fa[a] = 0, ch[b][0] = 0;
}
int fdr(int a) {
    access(a);
    while (1) {
        pushdown(a);
        if (ch[a][0])
            a = ch[a][0];
        else {
            splay(a);
            return a;
        }
    }
}
} // namespace LCT
vi out, in;
vi work(int n, vector<pi> eg, ll mx_ch = -1) {
    // mx_ch : max number of adding/replacing  default is (n + 100) * (n + 50)
    // n : number of vertices. 1-indexed.
    // eg: vector<pair<int, int> > storing all the edges.
    // return a vector<int> consists of all indices of vertices on the path. return empty list if
    // failed to find one.
    out.resize(n + 1), in.resize(n + 1);
    LCT::init(n);
    for (int i = 0; i <= n; i++) in[i] = out[i] = 0;
    if (mx_ch == -1) mx_ch = 1ll * (n + 100) * (n + 50); // default
    vector<vi> from(n + 1), to(n + 1);
    for (auto v : eg) from[v.fi].pb(v.se), to[v.se].pb(v.fi);
    unordered_set<int> canin, canout;
    for (int i = 1; i <= n; i++) canin.insert(i), canout.insert(i);
    mt19937 x(chrono::steady_clock::now().time_since_epoch().count());
    int tot = 0;
    while (mx_ch >= 0) {
        //    cout << tot << ' ' << mx_ch << endl;
        vector<pi> eg;
        for (auto v : canout)
            for (auto s : from[v])
                if (in[s] == 0) {
                    assert(canin.count(s));
                    continue;
                } else
                    eg.pb(mp(v, s));
        for (auto v : canin)
            for (auto s : to[v]) eg.pb(mp(s, v));
        shuffle(eg.begin(), eg.end(), x);
        if (eg.size() == 0) break;
        for (auto v : eg) {
            mx_ch--;
            if (in[v.se] && out[v.fi]) continue;
            if (LCT::fdr(v.fi) == LCT::fdr(v.se)) continue;
            if (in[v.se] || out[v.fi])
                if (x() & 1) continue;
            if (!in[v.se] && !out[v.fi]) tot++;
            if (in[v.se]) {
                LCT::cut(in[v.se], v.se);
                canin.insert(v.se);
                canout.insert(in[v.se]);
                out[in[v.se]] = 0;
                in[v.se]      = 0;
            }
            if (out[v.fi]) {
                LCT::cut(v.fi, out[v.fi]);
                canin.insert(out[v.fi]);
                canout.insert(v.fi);
                in[out[v.fi]] = 0;
                out[v.fi]     = 0;
            }
            LCT::link(v.fi, v.se);
            canin.erase(v.se);
            canout.erase(v.fi);
            in[v.se]  = v.fi;
            out[v.fi] = v.se;
        }
        if (tot == n - 1) {
            vi cur;
            for (int i = 1; i <= n; i++)
                if (!in[i]) {
                    int pl = i;
                    while (pl) {
                        cur.pb(pl), pl = out[pl];
                    }
                    break;
                }
            return cur;
        }
    }
    // failed to find a path
    return vi();
}
} // namespace hamil

void solve() {
    INT(n, m, k);
    VEC(Pii, edges, m);
    fori(i, m) {
        edges.push_back({edges[i].second, edges[i].first});
    }
    sort(all(edges));

    fori(k) {
        auto res = hamil::work(n, edges);
        print(res);

        vec(Pii, remove, 0);
        fori(i, n - 1) {
            remove.push_back({res[i], res[i + 1]});
            remove.push_back({res[i + 1], res[i]});
        }
        sort(all(remove));
        vec(Pii, new_edges, 0);
        int p = 0;
        for (auto e : edges) {
            if (p < remove.size() && e == remove[p]) {
                p++;
                continue;
            }
            new_edges.push_back(e);
        }
        edges = new_edges;
    }
}

int main() {
#ifndef INTERACTIVE
    cin.tie(0)->sync_with_stdio(0);
#endif
    // cout << fixed << setprecision(12);
    int t;
    t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

// // #pragma GCC target("avx2")
// // #pragma GCC optimize("O3")
// // #pragma GCC optimize("unroll-loops")
// // #define INTERACTIVE
//
// #include "kyopro-cpp/template.hpp"
//
// ////////// https://codeforces.com/blog/entry/90513
//
// namespace hamil {
// template <typename T>
// bool chkmax(T &x, T y) {
//     return x < y ? x = y, true : false;
// }
// template <typename T>
// bool chkmin(T &x, T y) {
//     return x > y ? x = y, true : false;
// }
// #define vi vector<int>
// #define pb push_back
// #define mp make_pair
// #define pi pair<int, int>
// #define fi first
// #define se second
// #define ll long long
// namespace LCT {
// vector<vi> ch;
// vi fa, rev;
// void init(int n) {
//     ch.resize(n + 1);
//     fa.resize(n + 1);
//     rev.resize(n + 1);
//     for (int i = 0; i <= n; i++) ch[i].resize(2), ch[i][0] = ch[i][1] = fa[i] = rev[i] = 0;
// }
// bool isr(int a) {
//     return !(ch[fa[a]][0] == a || ch[fa[a]][1] == a);
// }
// void pushdown(int a) {
//     if (rev[a]) {
//         rev[ch[a][0]] ^= 1, rev[ch[a][1]] ^= 1;
//         swap(ch[a][0], ch[a][1]);
//         rev[a] = 0;
//     }
// }
// void push(int a) {
//     if (!isr(a)) push(fa[a]);
//     pushdown(a);
// }
// void rotate(int a) {
//     int f = fa[a], gf = fa[f];
//     int tp  = ch[f][1] == a;
//     int son = ch[a][tp ^ 1];
//     if (!isr(f)) ch[gf][ch[gf][1] == f] = a;
//     fa[a] = gf;
//
//     ch[f][tp] = son;
//     if (son) fa[son] = f;
//
//     ch[a][tp ^ 1] = f, fa[f] = a;
// }
// void splay(int a) {
//     push(a);
//     while (!isr(a)) {
//         int f = fa[a], gf = fa[f];
//         if (isr(f))
//             rotate(a);
//         else {
//             int t1 = ch[gf][1] == f, t2 = ch[f][1] == a;
//             if (t1 == t2)
//                 rotate(f), rotate(a);
//             else
//                 rotate(a), rotate(a);
//         }
//     }
// }
// void access(int a) {
//     int pr = a;
//     splay(a);
//     ch[a][1] = 0;
//     while (1) {
//         if (!fa[a]) break;
//         int u = fa[a];
//         splay(u);
//         ch[u][1] = a;
//         a        = u;
//     }
//     splay(pr);
// }
// void makeroot(int a) {
//     access(a);
//     rev[a] ^= 1;
// }
// void link(int a, int b) {
//     makeroot(a);
//     fa[a] = b;
// }
// void cut(int a, int b) {
//     makeroot(a);
//     access(b);
//     fa[a] = 0, ch[b][0] = 0;
// }
// int fdr(int a) {
//     access(a);
//     while (1) {
//         pushdown(a);
//         if (ch[a][0])
//             a = ch[a][0];
//         else {
//             splay(a);
//             return a;
//         }
//     }
// }
// } // namespace LCT
// vi out, in;
// vi work(int n, vector<pi> eg, ll mx_ch = -1) {
//     // mx_ch : max number of adding/replacing  default is (n + 100) * (n + 50)
//     // n : number of vertices. 1-indexed.
//     // eg: vector<pair<int, int> > storing all the edges.
//     // return a vector<int> consists of all indices of vertices on the path. return empty list if
//     // failed to find one.
//     out.resize(n + 1), in.resize(n + 1);
//     LCT::init(n);
//     for (int i = 0; i <= n; i++) in[i] = out[i] = 0;
//     if (mx_ch == -1) mx_ch = 1ll * (n + 100) * (n + 50); // default
//     vector<vi> from(n + 1), to(n + 1);
//     for (auto v : eg) from[v.fi].pb(v.se), to[v.se].pb(v.fi);
//     unordered_set<int> canin, canout;
//     for (int i = 1; i <= n; i++) canin.insert(i), canout.insert(i);
//     mt19937 x(chrono::steady_clock::now().time_since_epoch().count());
//     int tot = 0;
//     while (mx_ch >= 0) {
//         //    cout << tot << ' ' << mx_ch << endl;
//         vector<pi> eg;
//         for (auto v : canout)
//             for (auto s : from[v])
//                 if (in[s] == 0) {
//                     assert(canin.count(s));
//                     continue;
//                 } else
//                     eg.pb(mp(v, s));
//         for (auto v : canin)
//             for (auto s : to[v]) eg.pb(mp(s, v));
//         shuffle(eg.begin(), eg.end(), x);
//         if (eg.size() == 0) break;
//         for (auto v : eg) {
//             mx_ch--;
//             if (in[v.se] && out[v.fi]) continue;
//             if (LCT::fdr(v.fi) == LCT::fdr(v.se)) continue;
//             if (in[v.se] || out[v.fi])
//                 if (x() & 1) continue;
//             if (!in[v.se] && !out[v.fi]) tot++;
//             if (in[v.se]) {
//                 LCT::cut(in[v.se], v.se);
//                 canin.insert(v.se);
//                 canout.insert(in[v.se]);
//                 out[in[v.se]] = 0;
//                 in[v.se]      = 0;
//             }
//             if (out[v.fi]) {
//                 LCT::cut(v.fi, out[v.fi]);
//                 canin.insert(out[v.fi]);
//                 canout.insert(v.fi);
//                 in[out[v.fi]] = 0;
//                 out[v.fi]     = 0;
//             }
//             LCT::link(v.fi, v.se);
//             canin.erase(v.se);
//             canout.erase(v.fi);
//             in[v.se]  = v.fi;
//             out[v.fi] = v.se;
//         }
//         if (tot == n - 1) {
//             vi cur;
//             for (int i = 1; i <= n; i++)
//                 if (!in[i]) {
//                     int pl = i;
//                     while (pl) {
//                         cur.pb(pl), pl = out[pl];
//                     }
//                     break;
//                 }
//             return cur;
//         }
//     }
//     // failed to find a path
//     return vi();
// }
// } // namespace hamil
//
// void solve() {
//     INT(n, m, k);
//     VEC(Pii, edges, m);
//     fori(i, m) {
//         edges.push_back({edges[i].second, edges[i].first});
//     }
//     sort(all(edges));
//
//     fori(k) {
//         auto res = hamil::work(n, edges);
//         print(res);
//
//         vec(Pii, remove, 0);
//         fori(i, n - 1) {
//             remove.push_back({res[i], res[i + 1]});
//             remove.push_back({res[i + 1], res[i]});
//         }
//         sort(all(remove));
//         vec(Pii, new_edges, 0);
//         int p = 0;
//         for (auto e : edges) {
//             if (p < remove.size() && e == remove[p]) {
//                 p++;
//                 continue;
//             }
//             new_edges.push_back(e);
//         }
//         edges = new_edges;
//     }
// }
//
// int main() {
// #ifndef INTERACTIVE
//     cin.tie(0)->sync_with_stdio(0);
// #endif
//     // cout << fixed << setprecision(12);
//     int t;
//     t = 1;
//     // cin >> t;
//     while (t--) solve();
//     return 0;
// }