// Uses Recursive-Largest-First (RLF) algorithm for graph coloring.
#include <bits/stdc++.h>
using namespace std;

vector<int> rlf(const vector<vector<int>> &adj) {
  int n = (int)adj.size();
  vector<int> color(n, -1);

  for (int current_color = 0;; current_color++) {
    int start = -1;
    for (int i = 0; i < n; i++) {
      if (color[i] != -1)
        continue;
      if (start == -1 || adj[i].size() > adj[start].size())
        start = i;
    }
    if (start == -1)
      break; // All vertices colored.

    color[start] = current_color;

    set<int> candidates;
    for (int i = 0; i < n; i++) {
      if (color[i] == -1)
        candidates.insert(i);
    }
    for (int v : adj[start])
      candidates.erase(v);

    vector<int> neighbours_near_S_count(n, 0);
    for (int u : adj[start])
      for (int v : adj[u])
        neighbours_near_S_count[v]++;

    while (!candidates.empty()) {
      // Find candidate with most neighbors in color class.
      int best_candidate =
          *min_element(candidates.begin(), candidates.end(), [&](int a, int b) {
            if (neighbours_near_S_count[a] != neighbours_near_S_count[b])
              return neighbours_near_S_count[a] > neighbours_near_S_count[b];
            return adj[a].size() - neighbours_near_S_count[a] <
                   adj[b].size() - neighbours_near_S_count[b];
          });
      color[best_candidate] = current_color;
      candidates.erase(best_candidate);
      for (int v : adj[best_candidate]) {
        candidates.erase(v);
        for (int u : adj[v]) {
          neighbours_near_S_count[u]++;
        }
      }
    }
  }
  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 = rlf(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;
  }
}