#include <bits/stdc++.h>

using namespace std;

const int N = 6e5 + 5;

struct edge {
    int num, to;
    edge(int num, int to) : num(num), to(to) { }
};

int n, m, p, T, C, timer, id_color = 1, link[N], tin[N], fup[N], color[N], cnt[N];
bool block[N];
vector<pair<int, int> > E;

vector<int> t[N];
vector<edge> g[N];

void read() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        E.push_back({a, b});
    }
    scanf("%d", &T);
}

bool fn(int n) {
    if (n > 2) return false;
    if (n == 1)
        printf("0");
    else {
        if (m >= 2)
            printf("0");
        else {
            printf("1\n");
            if (T == 1)
                printf("1 2");
        }
    }
    return true;
}

void dfs_bridge(int v, int last_num = -1) {
    fup[v] = tin[v] = ++timer;
    for (auto& edge: g[v]) {
        int to = edge.to, num = edge.num;
        if (num == last_num) continue;
        if (tin[to])
            fup[v] = min(fup[v], tin[to]);
        else {
            dfs_bridge(to, num);
            fup[v] = min(fup[v], fup[to]);
            if (tin[v] < fup[to])
                block[num] = true;
        }
    }
}

void dfs_tree(int v, int cur_color = 1) {
    color[v] = cur_color;
    link[color[v]] = v;
    for (auto& edge: g[v]) {
        int to = edge.to, num = edge.num;
        if (color[to]) continue;
        if (!block[num])
            dfs_tree(to, cur_color);
        else {
            int cur_color = ++id_color;
            int a = color[v], b = cur_color;
            t[a].push_back(b);
            t[b].push_back(a);
            dfs_tree(to, cur_color);
        }
    }
}

int find_cnt(int v, int last = -1) {
    bool leaf = true;
    for (auto to: t[v])
        if (to != last) {
            cnt[v] += find_cnt(to, v);
            leaf = false;
        }
    if (leaf) cnt[v] = 1;
    return cnt[v];
}

void find_centroid(int v, int last = -1) {
    pair<int, int> Max = {0, 0};
    for (auto to: t[v])
        if (to != last)
            Max = max(Max, make_pair(cnt[to], to));
    if (Max.first > (p + 1) / 2)
        find_centroid(Max.second, v);
    else
        C = v;
}

void find_leaves(auto& q, int v, int last) {
    bool leaf = true;
    for (auto to: t[v])
        if (to != last) {
            leaf = false;
            find_leaves(q, to, v);
        }
    if (leaf) q.push_back(v);
}

auto find_res(int v) {
    vector<vector<int> > q;
    int k = 0;
    for (auto to: t[v]){
        vector<int> tmp;
        find_leaves(tmp, to, v);
        q.push_back(tmp);
        k += 1;
    }
    vector<pair<int, int> > res;
    set<pair<int, int> > st;
    for (int i = 0; i < k; ++i)
        st.insert({(int)q[i].size(), i});
    int last = 0;
    while (st.size() > 1) {
        int a = st.begin() -> second;
        int b = st.rbegin() -> second;
        st.erase(st.begin());
        st.erase(*st.rbegin());
        int v = link[q[a].back()];
        int u = link[q[b].back()];
        res.push_back({v, u});
        q[a].pop_back();
        q[b].pop_back();
        if (!q[a].empty())
            st.insert({(int)q[a].size(), a});
        else
            last = v;
        if (!q[b].empty())
            st.insert({(int)q[b].size(), b});
        else
            last = u;
    }
    if (!st.empty()) {
        auto& tmp = q[st.begin() -> second];
        while (!tmp.empty()) {
            int v = tmp.back();
            res.push_back({link[v], last});
            tmp.pop_back();
        }
    }
    return res;
}

void solve() {
    read();
    if (fn(n)) return;
    for (int i = 0; i < m; ++i) {
        int a = E[i].first, b = E[i].second;
        g[a].push_back(edge(i, b));
        g[b].push_back(edge(i, a));
    }

    srand(time(nullptr));

    dfs_bridge(1);
    dfs_tree(1);

    n = id_color;
    int k = 0;
    for (int i = 1; i <= n; ++i)
        k += t[i].size() == 1;

    printf("%d\n", (k + 1) / 2);
    if (T == 1) {
        if (n == 2) {
            int a = 1, b = t[1].front();
            printf("%d %d", link[a], link[b]);
            return;
        }
        int v = 0;
        for (int i = 1; i <= n; ++i)
            if (t[i].size() != 1)
                v = i;
        find_cnt(v);
        p = cnt[v];
        find_centroid(v);
        auto res = find_res(C);
        assert(res.size() == (k + 1) / 2);
        for (auto it: res)
            printf("%d %d\n", it.first, it.second);
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    solve();
    return 0;
}