// Uses DSATUR algorithm for graph coloring.
#include <bits/stdc++.h>
using namespace std;

vector<int> dsatur(const vector<vector<int>> &adj) {
  int n = (int)adj.size();
  vector<int> color(n, -1);
  vector<int> degree(n);
  for (int i = 0; i < n; i++)
    degree[i] = (int)adj[i].size();
  vector<int> saturation(n, 0);
  set<tuple<int, int, int>> pq; // (-saturation, -degree, node)
  for (int i = 0; i < n; i++)
    pq.emplace(0, -degree[i], i);

  for (int iter = 0; iter < n; iter++) {
    auto [sat, deg, u] = *pq.begin();
    pq.erase(pq.begin());
    // Find the smallest color not used by neighbors.
    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;

    // Update saturation of neighbors.
    for (int v : adj[u]) {
      if (color[v] == -1) {
        pq.erase(make_tuple(-saturation[v], -degree[v], v));
        saturation[v]++;
        pq.emplace(-saturation[v], -degree[v], v);
      }
    }
  }
  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 = dsatur(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;
  }
}