package nl.camilstaps.cs;

import nl.camilstaps.cs.graphs.Graph;
import nl.camilstaps.cs.graphs.Node;

import java.util.Scanner;

/**
 * Solution for the Garbage Collection problem.
 *
 * @author Camil Staps
 */
class GarbageCollectionHelper {

    /**
     * Read in a Graph from stdin and print whether we can place N bins to stdout
     * @param args
     */
    public static void main(String[] args) {
        Graph graph = new Graph();
        int n_bins = readGraph(new Scanner(System.in), graph);
        System.out.println(graph.maximumIndependentSetSize() >= n_bins ? "possible" : "impossible");
    }

    /**
     * Read a Graph in the defined format:
     *
     *      [n_edges] [n_nodes] [n_bins]
     *      [fst] [snd]
     *      [fst] [snd]
     *      [fst] [snd]
     *      ...
     *
     * @param sc the Scanner to use
     * @param graph the Graph to build
     * @return the number of bins
     */
    private static int readGraph(Scanner sc, Graph graph) {
        int n_edges = sc.nextInt();
        int n_nodes = sc.nextInt();
        int n_bins  = sc.nextInt();

        for (int i = 1; i <= n_nodes; i++) {
            graph.addNode(new Node(i));
        }

        for (int i = 0; i < n_edges; i++) {
            int fst = sc.nextInt();
            int snd = sc.nextInt();
            graph.getNode(fst - 1).getNeighbourhood().add(graph.getNode(snd - 1));
            graph.getNode(snd - 1).getNeighbourhood().add(graph.getNode(fst - 1));
        }

        return n_bins;
    }

}