#include <bits/stdc++.h>
using namespace std;
template <class T, class U, class V>
inline bool inRange(T a, U b, V c) {
  return b <= a && a <= c;
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline void MAX(T &a, T b) {
  a = max(a, b);
}
template <class T>
inline void MIN(T &a, T b) {
  a = min(a, b);
}
template <class T, class V>
pair<T, V> operator+(pair<T, V> a, pair<T, V> b) {
  return {a.first + b.first, a.second + b.second};
}
template <class T, class V>
pair<T, V> operator-(pair<T, V> a, pair<T, V> b) {
  return {a.first - b.first, a.second - b.second};
}
template <class T = int>
inline bool io(T &res) {
  static char c = ' ';
  if (c == -1) return 0;
  while (!inRange(c, '0', '9')) c = getchar_unlocked();
  if (c == -1) return 0;
  res = c - '0';
  while ((c = getchar_unlocked()), inRange(c, '0', '9')) {
    res = (res << 3) + (res << 1) + c - '0';
  }
  return 1;
}
inline string getString() {
  char buff[1000006];
  scanf("%s", buff);
  return buff;
}
inline void open(string a) {
  freopen((a + ".in").c_str(), "r", stdin);
  freopen((a + ".out").c_str(), "w", stdout);
}
inline void close() {
  fclose(stdin);
  fclose(stdout);
}
const int MAGIC_MEMSET_CONST = 63;
const int INF = 1061109567;
const long long LINF = 4557430888798830399LL;
const double DINF = numeric_limits<double>::infinity();
const int INV = -1044266559;
const long long LINV = -4485090715960753727LL;
const double DINV = -DINF;
const int MOD = (int)1e9 + 7;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
set<pair<int, int> > st;
int memo[300005];
int par[300005];
vector<pair<int, int> > res;
int getpar(int i) { return par[i] == i ? i : par[i] = getpar(par[i]); }
int main() {
  if (!0) {
    ios_base::sync_with_stdio(false);
    std::cin.tie(0);
  }
  int n, m, k, push;
  cin >> n >> m >> k;
  push = 0;
  iota(par, par + n + 1, 0);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    st.insert({a, b});
    st.insert({b, a});
  }
  set<int> rip;
  for (int i = 2; i <= n; i++) rip.insert(i);
  for (int i = 2; i <= n; i++)
    if (rip.count(i)) {
      queue<int> q;
      q.push(i);
      rip.erase(i);
      while (!q.empty()) {
        set<int> tmp;
        int cur = q.front();
        q.pop();
        for (int j : rip) {
          if (st.count({cur, j}))
            tmp.insert(j);
          else
            par[getpar(cur)] = getpar(j), res.push_back({cur, j}), q.push(j);
        }
        rip = tmp;
      }
    }
  int cntr = 0;
  int cntr2 = 0;
  for (int i = 2; i <= n; i++) {
    if (par[i] == i) cntr++;
    if (!memo[getpar(i)]) {
      if (!st.count({1, i})) {
        res.push_back({1, i});
        k--;
        memo[getpar(i)] = 1;
        cntr2++;
        st.insert({1, i});
      }
    }
  }
  if (cntr != cntr2) {
    cout << (push ? "-1" : "impossible") << endl;
    return 0;
  }
  for (int i = 2; i <= n && k > 0; i++) {
    if (!st.count({1, i})) {
      res.push_back({1, i});
      k--;
    }
  }
  if (k != 0) {
    cout << (push ? "-1" : "impossible") << endl;
    return 0;
  }
  if (!push)
    cout << "possible" << endl;
  else {
    for (pair<int, int> i : res) {
      cout << i.first << ' ' << i.second << endl;
    }
  }
  return 0;
}
