A tree is a connected undirected graph consisting of n vertices and n - 1 edges. Vertices are numbered 1 through n.

Limak is a little polar bear. He once had a tree with n vertices but he lost it. He still remembers something about the lost tree though.

You are given m pairs of vertices (a1, b1), (a2, b2), ..., (am, bm). Limak remembers that for each i there was no edge between ai and bi. He also remembers that vertex 1 was incident to exactly k edges (its degree was equal to k).

Is it possible that Limak remembers everything correctly? Check whether there exists a tree satisfying the given conditions.

Input

The first line of the input contains three integers n, m and k (<image>) — the number of vertices in Limak's tree, the number of forbidden pairs of vertices, and the degree of vertex 1, respectively.

The i-th of next m lines contains two distinct integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the i-th pair that is forbidden. It's guaranteed that each pair of vertices will appear at most once in the input.

Output

Print "possible" (without quotes) if there exists at least one tree satisfying the given conditions. Otherwise, print "impossible" (without quotes).

Examples

Input

5 4 2
1 2
2 3
4 2
4 1


Output

possible


Input

6 5 3
1 2
1 3
1 4
1 5
1 6


Output

impossible

Note

In the first sample, there are n = 5 vertices. The degree of vertex 1 should be k = 2. All conditions are satisfied for a tree with edges 1 - 5, 5 - 2, 1 - 3 and 3 - 4.

In the second sample, Limak remembers that none of the following edges existed: 1 - 2, 1 - 3, 1 - 4, 1 - 5 and 1 - 6. Hence, vertex 1 couldn't be connected to any other vertex and it implies that there is no suitable tree.
import java.io.*;
import java.util.*;

public class CF {
	FastScanner in;
	PrintWriter out;

	int[] p;

	int get(int x) {
		return p[x] == x ? x : (p[x] = get(p[x]));
	}

	void unite(int x, int y) {
		p[get(x)] = get(y);
	}

	class SegmentTree {
		int[] ids;

		SegmentTree(int n) {
			ids = new int[n * 4];
			Arrays.fill(ids, -1);
		}

		void set(int v, int l, int r, int needL, int needR, int val) {
			if (needL > needR) {
				return;
			}
			if (needL == l && needR == r) {
				if (ids[v] == -1) {
					ids[v] = val;
				} else {
					unite(ids[v], val);
				}
			} else {
				int m = (l + r) >> 1;
				set(v * 2 + 1, l, m, needL, Math.min(needR, m), val);
				set(v * 2 + 2, m + 1, r, Math.max(m + 1, needL), needR, val);
			}
		}

		void go(int v, int l, int r) {
			if (l == r) {
				return;
			}
			if (ids[v] != -1) {
				if (ids[v * 2 + 1] == -1) {
					ids[v * 2 + 1] = ids[v];
				} else {
					unite(ids[v], ids[v * 2 + 1]);
				}
				if (ids[v * 2 + 2] == -1) {
					ids[v * 2 + 2] = ids[v];
				} else {
					unite(ids[v], ids[v * 2 + 2]);
				}
			}
			int m = (l + r) >> 1;
			go(v * 2 + 1, l, m);
			go(v * 2 + 2, m + 1, r);
		}
	}

	void solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		int k = in.nextInt();
		ArrayList<Integer>[] g = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			int fr = in.nextInt() - 1;
			int to = in.nextInt() - 1;
			g[fr].add(to);
			g[to].add(fr);
		}
		for (int i = 1; i < n; i++) {
			g[i].add(-1);
			g[i].add(n);
			Collections.sort(g[i]);
		}
		p = new int[n];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
		SegmentTree st = new SegmentTree(n);
		for (int i = 0; i < n; i++) {
			st.set(0, 0, n - 1, i, i, i);
		}
		for (int i = 1; i < n; i++) {
			for (int j = 0; j + 1 < g[i].size(); j++) {
				int fr = g[i].get(j) + 1;
				fr = Math.max(fr, 1);
				int to = g[i].get(j + 1) - 1;
				if (fr <= to) {
					st.set(0, 0, n - 1, fr, to, i);
				}
			}
		}
		st.go(0, 0, n - 1);
		ArrayList<Integer>[] all = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			all[i] = new ArrayList<>();
		}
		for (int i = 1; i < n; i++) {
			all[get(i)].add(i);
		}
		int groups = 0;
		boolean[] canFirst = new boolean[n];
		Arrays.fill(canFirst, true);
		for (int to : g[0]) {
			canFirst[to] = false;
		}
		for (int i = 0; i < n; i++) {
			if (all[i].size() == 0) {
				continue;
			}
			boolean can = false;
			for (int v : all[i]) {
				if (canFirst[v]) {
					can = true;
				}
			}
			if (!can) {
				out.println("impossible");
				return;
			}
			groups++;
		}
		out.println(groups <= k && (n - 1 - g[0].size() >= k) ? "possible"
				: "impossible");
	}

	void run() {
		try {
			in = new FastScanner(new File("test.in"));
			out = new PrintWriter(new File("test2.out"));

			solve();

			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	void runIO() {

		in = new FastScanner(System.in);
		out = new PrintWriter(System.out);

		solve();

		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	public static void main(String[] args) {
		new CF().runIO();
	}
}