#include <array>
#include <iostream>
#include <vector>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;

struct TwoSat {
	int N;
	vector<vi> gr;
	vi values; // 0 = false, 1 = true

	TwoSat(int n = 0) : N(n), gr(2*n) {}

	int addVar() { // (optional)
		gr.emplace_back();
		gr.emplace_back();
		return N++;
	}

	void either(int f, int j) {
		f = max(2*f, -1-2*f);
		j = max(2*j, -1-2*j);
		gr[f].push_back(j^1);
		gr[j].push_back(f^1);
	}
	void setValue(int x) { either(x, x); }

	void atMostOne(const vi& li) { // (optional)
		if (sz(li) <= 1) return;
		int cur = ~li[0];
		rep(i,2,sz(li)) {
			int next = addVar();
			either(cur, ~li[i]);
			either(cur, next);
			either(~li[i], next);
			cur = ~next;
		}
		either(cur, ~li[1]);
	}

	vi val, comp, z; int time = 0;
	int dfs(int i) {
		int low = val[i] = ++time, x; z.push_back(i);
		for(int e : gr[i]) if (!comp[e])
			low = min(low, val[e] ?: dfs(e));
		if (low == val[i]) do {
			x = z.back(); z.pop_back();
			comp[x] = low;
			if (values[x>>1] == -1)
				values[x>>1] = x&1;
		} while (x != i);
		return val[i] = low;
	}

	bool solve() {
		values.assign(N, -1);
		val.assign(2*N, 0); comp = val;
		rep(i,0,2*N) if (!comp[i]) dfs(i);
		rep(i,0,N) if (comp[2*i] == comp[2*i+1]) return 0;
		return 1;
	}
};

int main() {
  int n, k, m;
  cin >> n >> k >> m;
  vector<vector<int>> edges(n);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  int maxv = 1;
  for(int i = 0; i < k; i++) maxv *= 3;
  for(int mask = 0; mask < maxv; mask++) {
    vector<array<int, 2>> color(n);
    {
      int t = mask;
      for(int i = 0; i < k; i++) {
        color[i] = {t%3, t%3};
        t /= 3;
      }
    }
    for(int i = 0; i < k; i++) {
      for(int j: edges[i]) {
        if(j >= k) {
          color[j] = {(color[i][0]+1)%3, (color[i][0]+2)%3};
        }
      }
    }
    TwoSat twosat(n);
    for(int i = 0; i < n; i++) for(int j: edges[i]) {
      if(color[i][0] == color[j][0]) twosat.either(i, j);
      if(color[i][0] == color[j][1]) twosat.either(i, ~j);
      if(color[i][1] == color[j][0]) twosat.either(~i, j);
      if(color[i][1] == color[j][1]) twosat.either(~i, ~j);
    }
    if(twosat.solve()) {
      cout << "possible\n";
      for(int i = 0; i < n; i++) {
        cout << ((twosat.values[i] ? color[i][1] : color[i][0]) + 1) << " \n"[i == n-1];
      }
      return 0;
    }
  }
  cout << "impossible\n";
}