#include <bits/stdc++.h>

using namespace std;

// BEGIN KACTL MACROS AND 2SAT

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#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;
	}
};

// END KACTL MACROS AND 2SAT


int main() {
  int N, M, K;
  cin >> N >> K >> M;

	// just need a list of edges
  vector<pair<int,int>> e(M);

  for (auto& [u,v] : e) {
    cin >> u >> v;
    --u; --v;
  }

	// 3^K
  int maxC = 1;
  for (int i = 0; i < K; ++i) maxC *= 3;

	// clr[u][0] and clr[u][1] will be the only
	// two possible colours for employee u
	// (it could be they are both the same colour,
	// so really only one works)
  vector<vector<int>> clr(N);

	// the base-3 expansion of S is proposing
	// a colouring of the executives
  for (int S = 0; S < maxC; ++S) {
		// T%3 will be the colour for executive u
    for (int u = 0, T = S; u < K; ++u, T /= 3) clr[u] = {T%3, T%3};

		// for every non-executive employee u, find a neighbouring executive and
		// set the valid colours for u to be the others apart from the exec's colours
		for (auto [u,v] : e) {
      if (u < K && v >= K)
        clr[v] = {(clr[u][0]+1)%3, (clr[u][0]+2)%3};
		}
    
    // x[u] == false means use colour clr[u][0]
    // x[u] == true means use colour clr[u][1]
		// constraints == endpoints don't get the same colour
    TwoSat sat(N);
    for (auto [u,v] : e) {
      if (clr[u][0] == clr[v][0]) sat.either(u,v);
      if (clr[u][0] == clr[v][1]) sat.either(u,~v);
      if (clr[u][1] == clr[v][0]) sat.either(~u,v);
      if (clr[u][1] == clr[v][1]) sat.either(~u,~v);
    }

    if (sat.solve()) {
      cout << "possible" << endl;
			for (int u = 0; u < N; ++u) cout << clr[u][sat.values[u]]+1 << (u+1==N?'\n':' ');
      exit(0);
    }
    
  }

  cout << "impossible" << endl;

  return 0;
}