# Intentionally unoptimized solution
# - Always runs in theta(3^k * (n + m)) time, never early exits

from typing import List, Optional, Tuple
import itertools
import random  # For randomly selecting a valid answer
import sys

sys.setrecursionlimit(10**5)


class TwoSATSolver:
  def __init__(self, n: int):
    self.n = n
    self.adj = [[] for _ in range(2 * n)]
    self.adj_rev = [[] for _ in range(2 * n)]
    self.visited = [False] * (2 * n)
    self.order = []
    self.component = [-1] * (2 * n)

  def add_clause(self, i: int, f_i: bool, j: int, f_j: bool) -> None:
    self._add_implication(i, not f_i, j, f_j)
    self._add_implication(j, not f_j, i, f_i)

  def solve(self) -> Optional[List[bool]]:
    for v in range(2 * self.n):
      if not self.visited[v]:
        self._dfs1(v)
    label = 0
    for v in reversed(self.order):
      if self.component[v] == -1:
        self._dfs2(v, label)
        label += 1
    assignment = [False] * self.n
    for i in range(self.n):
      if self.component[2 * i] == self.component[2 * i + 1]:
        return None
      assignment[i] = self.component[2 * i] > self.component[2 * i + 1]
    return assignment

  def _add_implication(self, i: int, f_i: bool, j: int, f_j: bool) -> None:
    self.adj[2 * i + (0 if f_i else 1)].append(2 * j + (0 if f_j else 1))
    self.adj_rev[2 * j + (0 if f_j else 1)].append(2 * i + (0 if f_i else 1))

  def _dfs1(self, v: int) -> None:
    self.visited[v] = True
    for u in self.adj[v]:
      if not self.visited[u]:
        self._dfs1(u)
    self.order.append(v)

  def _dfs2(self, v: int, label: int) -> None:
    self.component[v] = label
    for u in self.adj_rev[v]:
      if self.component[u] == -1:
        self._dfs2(u, label)


def do_single_assignment(n: int, edges: List[Tuple[int, int]], exec_colors: List[int], managers: List[int]) -> Optional[List[int]]:
  solver = TwoSATSolver(n)
  for u, v in edges:
    if u < len(exec_colors): continue  # exec coloring is handled below
    if exec_colors[managers[u]] == exec_colors[managers[v]]:
      solver.add_clause(u, True, v, True)
      solver.add_clause(u, False, v, False)
    elif (exec_colors[managers[u]] + 1) % 3 == exec_colors[managers[v]]:
      solver.add_clause(u, True, v, False)
    elif (exec_colors[managers[u]] + 2) % 3 == exec_colors[managers[v]]:
      solver.add_clause(u, False, v, True)
    else:
      raise ValueError("Unexpected color configuration")

  for u, v in edges:
    if u >= len(exec_colors): continue  # nonexec-to-nonexec coloring handled above
    if v < len(exec_colors): continue  # exec-to-exec coloring is fixed (and enforced elsewhere)
    if exec_colors[u] == exec_colors[managers[v]]: continue # No extra constraints
    if (exec_colors[u] + 1) % 3 == exec_colors[managers[v]]:
      solver.add_clause(v, True, v, True)
    elif (exec_colors[u] + 2) % 3 == exec_colors[managers[v]]:
      solver.add_clause(v, False, v, False)
    else:
      raise ValueError("Unexpected color configuration")
      

  assignment = solver.solve()
  if assignment is None:
    return None

  coloring = [None] * n
  for i in range(n):
    if i < len(exec_colors):
      coloring[i] = exec_colors[i]
    else:
      coloring[i] = (exec_colors[managers[i]] + (1 if assignment[i] else 2)) % 3
  return coloring

def valid_coloring(coloring: List[int], edges: List[Tuple[int, int]]) -> bool:
  for u, v in edges:
    if coloring[u] == coloring[v]:
      return False
  return True


def do_case(n: int, k: int, edges: List[Tuple[int, int]]) -> Optional[List[int]]:
  # Assign a manager to each employee, doesn't matter which one, just some connected one.
  managers = [None] * n
  for i in range(k):
    managers[i] = i
  for u, v in edges:
    if u < k and v >= k:
      managers[v] = u

  answers = []
  for assignment in itertools.product([0, 1, 2], repeat=k):
    result = do_single_assignment(n, edges, list(assignment), managers)
    if result is not None and valid_coloring(result, edges):
      answers.append([x + 1 for x in result])
  
  if not answers:
    return None
  random.seed(123852)
  return random.choice(answers)


n, k, m = map(int, input().split())
edges = [tuple(x - 1 for x in map(int, input().split())) for _ in range(m)]

ans = do_case(n, k, edges)
if ans is None:
  print("impossible")
else:
  print("possible")
  print(" ".join(map(str, ans)))