#include<bits/stdc++.h>
#define rep(i,j,k) for (int i=j;i<(k);++i)
using namespace std;

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

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

	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 n, k, m;
vector<vi> edges;

vi solve(vi execs) {
    vi possib(n, 7);

    rep(ei,0,k) {
        int mask = 1<<execs[ei];
        possib[ei] &= mask;

        mask^=7;
        for (auto oi : edges[ei]) possib[oi]&=mask;
    }

    vector<vi> ops(n);

    rep(i,0,n) {
        rep(j,0,3) if (possib[i]&(1<<j)) ops[i].push_back(j);
        if (ops[i].size() == 0) return {};
        else if (ops[i].size() == 1) ops[i].push_back(ops[i][0]); // duplicate for simplicity, could be more efficient
        assert (ops[i].size() == 2);
    }

    TwoSat solver(n);

    rep(i,0,n) {
        for (auto oi : edges[i]) {
            if (ops[i][0] == ops[oi][0]) solver.either(i, oi);
            if (ops[i][0] == ops[oi][1]) solver.either(i, ~oi);
            if (ops[i][1] == ops[oi][0]) solver.either(~i, oi);
            if (ops[i][1] == ops[oi][1]) solver.either(~i, ~oi);
        }
    }

    if (!solver.solve()) return {};

    vi ans(n);

    rep(i,0,n) ans[i] = ops[i][solver.values[i]];

    return ans;
}

int main() {
    cin >> n >> k >> m;

    edges.resize(n);

    while (m--) {
        int u, v;
        cin >> u >> v;
        --u,--v;

        if (u>v) swap(u,v);
        edges[u].push_back(v);
    }

    int cap=1;
    rep(_,0,k) cap*=3;

    for(int mask=0;mask<cap;mask+=3) {
        // slight optimization here, execs[0]==0 and execs[1]!=2
        if (mask%9==6) continue;

        vi execs(k);
        int smask = mask;
        rep(i,0,k) execs[i]=smask%3,smask/=3;

        vi ans = solve(execs);

        if (ans.size()) {
            cout << "possible\n";
            for (auto x : ans) cout << (x+1) << ' '; cout << endl;
            return 0;
        }
    }

    cout << "impossible\n";

    return 0;
}