// Uses a greedy algorithm for graph coloring.
// In particular, picks a permutation of the nodes and colors them in
// that order, using the smallest available color each time.
//
// Instead of randomizing, it just picks a couple common permutations they might
// use:
//
// - Sorted by degree (ascending)
// - Sorted by degree (descending)
// - Sorted by index (ascending)
// - Sorted by index (descending)
// - Sorted by degree (ascending), but do all execs first (ascending)
#include <bits/stdc++.h>
using namespace std;

vector<int> actual_greedy(const vector<vector<int>> &adj,
                          const vector<int> &perm) {
  int n = (int)adj.size();

  vector<int> color(n, -1);
  for (int idx = 0; idx < n; idx++) {
    int u = perm[idx];
    set<int> used;
    for (int v : adj[u]) {
      if (color[v] != -1)
        used.insert(color[v]);
    }
    int c = 0;
    while (used.count(c))
      c++;
    color[u] = c;
  }
  return color;
}

vector<int> greedy(const vector<vector<int>> &adj, int k) {
  int n = (int)adj.size();
  vector<int> perm(n);
  iota(perm.begin(), perm.end(), 0);

  { // Sorted by index ascending.
    vector<int> color = actual_greedy(adj, perm);
    if (*max_element(color.begin(), color.end()) < 3)
      return color;
  }

  { // Sorted by index descending.
    reverse(perm.begin(), perm.end());
    vector<int> color = actual_greedy(adj, perm);
    if (*max_element(color.begin(), color.end()) < 3)
      return color;
  }
  { // Sorted by degree ascending.
    sort(perm.begin(), perm.end(),
         [&](int a, int b) { return adj[a].size() < adj[b].size(); });
    vector<int> color = actual_greedy(adj, perm);
    if (*max_element(color.begin(), color.end()) < 3)
      return color;
  }
  { // Sorted by degree descending.
    sort(perm.begin(), perm.end(),
         [&](int a, int b) { return adj[a].size() > adj[b].size(); });
    vector<int> color = actual_greedy(adj, perm);
    if (*max_element(color.begin(), color.end()) < 3)
      return color;
  }
  { // Sorted by degree ascending, but do all execs first (ascending).
    sort(perm.begin(), perm.end(), [&](int a, int b) {
      if (a < k && b < k)
        return adj[a].size() < adj[b].size();
      if (a < k)
        return true;
      if (b < k)
        return false;
      return adj[a].size() < adj[b].size();
    });
    vector<int> color = actual_greedy(adj, perm);
    if (*max_element(color.begin(), color.end()) < 3)
      return color;
  }
  return vector<int>(n, 3); // Impossible.
}

int main() {
  int n, k, m;
  cin >> n >> k >> m;
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  vector<int> color = greedy(adj, k);
  if (*max_element(color.begin(), color.end()) >= 3) {
    cout << "impossible" << endl;
  } else {
    cout << "possible" << endl;
    for (int i = 0; i < n; i++)
      cout << (i ? " " : "") << color[i] + 1;
    cout << endl;
  }
}