// Uses a greedy algorithm for graph coloring.
// In particular, picks a random permutation of the nodes and colors them in
// that order, using the smallest available color each time.
#include <bits/stdc++.h>
using namespace std;

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

  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;
}

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);
  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;
  }
}