Problem: It's the year 5555. You have a graph, and you want to find a long cycle and a huge independent set, just because you can. But for now, let's just stick with finding either.

Given a connected graph with n vertices, you can choose to either:

  * find an independent set that has exactly ⌈√{n}⌉ vertices.
  * find a simple cycle of length at least ⌈√{n}⌉. 



An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice. I have a proof you can always solve one of these problems, but it's too long to fit this margin.

Input

The first line contains two integers n and m (5 ≤ n ≤ 10^5, n-1 ≤ m ≤ 2 ⋅ 10^5) — the number of vertices and edges in the graph.

Each of the next m lines contains two space-separated integers u and v (1 ≤ u,v ≤ n) that mean there's an edge between vertices u and v. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

Output

If you choose to solve the first problem, then on the first line print "1", followed by a line containing ⌈√{n}⌉ distinct integers not exceeding n, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print "2", followed by a line containing one integer, c, representing the length of the found cycle, followed by a line containing c distinct integers integers not exceeding n, the vertices in the desired cycle, in the order they appear in the cycle.

Examples

Input


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


Output


1
1 6 4

Input


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


Output


2
4
1 5 2 4

Input


5 4
1 2
1 3
2 4
2 5


Output


1
3 4 5 

Note

In the first sample:

<image>

Notice that you can solve either problem, so printing the cycle 2-4-3-1-5-6 is also acceptable.

In the second sample:

<image>

Notice that if there are multiple answers you can print any, so printing the cycle 2-5-6, for example, is acceptable.

In the third sample:

<image>

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.HashSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FEhabsLastTheorem solver = new FEhabsLastTheorem();
        solver.solve(1, in, out);
        out.close();
    }

    static class FEhabsLastTheorem {
        PrintWriter out;
        InputReader in;
        ArrayList<Integer>[] graph;
        HashSet<Integer>[] tset;
        int[] par;
        int[] dep;
        int max_cycle = 0;
        int start = 0;
        int end = 0;
        DSU ob;
        boolean[] visited;
        int[] tin;
        int[] low;
        int timer = 0;
        int[] cnt = new int[2];

        void dfs(int v, int p, int h) {
            dep[v] = h;
            for (int u : graph[v]) {
                if (dep[u] == -1) {
                    par[u] = v;
                    dfs(u, v, h + 1);
                } else if (u != par[v]) {
                    if (dep[v] - dep[u] + 1 > max_cycle) {
                        max_cycle = dep[v] - dep[u] + 1;
                        start = v;
                        end = u;
                    }
                }
            }
        }

        void tarjan(int v, int p) {
            visited[v] = true;
            tin[v] = low[v] = timer++;
            for (int u : graph[v]) {
                int to = u;
                if (to == p) continue;
                if (visited[to]) {
                    low[v] = Math.min(low[v], tin[to]);
                } else {
                    tarjan(to, v);
                    low[v] = Math.min(low[v], low[to]);
                    if (low[to] > tin[v]) {
                        //its a bridge
                    } else {
                        ob.unite(to, v);
                    }
                }
            }
        }

        void dfs2(int v, int p, int h) {
            dep[v] = h;
            cnt[h % 2]++;
            for (int u : tset[v]) {
                if (u != p)
                    dfs2(u, v, h + 1);
            }
        }

        TreeSet<Integer> MIS(int n) {
            TreeSet<Integer> is = new TreeSet<>();
            TreeSet<Pair> set = new TreeSet<>();
            int deg[] = new int[n + 1];
            for (int i = 0; i < n; ++i) {
                set.add(new Pair(graph[i].size(), i));
                deg[i] = graph[i].size();
            }
            while (!set.isEmpty()) {
                Pair v = set.pollFirst();
                for (int e : graph[v.y]) {
                    if (set.contains(new Pair(deg[e], e))) {
                        for (int f : graph[e]) {
                            if (set.contains(new Pair(deg[f], f))) {
                                set.remove(new Pair(deg[f], f));
                                set.add(new Pair(--deg[f], f));
                            }
                        }
                        set.remove(new Pair(deg[e], e));
                    }
                }
                is.add(v.y);
            }
            return is;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.out = out;
            this.in = in;
            int n = ni();
            int m = ni();
            visited = new boolean[n];
            low = new int[n];
            tin = new int[n];
            ob = new DSU(n);
            graph = new ArrayList[n];
            tset = new HashSet[n];
            par = new int[n];
            dep = new int[n];
            int sq = (int) Math.sqrt(n);
            if (sq * sq != n)
                sq++;
            int i = 0;
            for (i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
                tset[i] = new HashSet<>();
            }
            Arrays.fill(dep, -1);
            for (i = 0; i < m; i++) {
                int u = ni() - 1;
                int v = ni() - 1;
                graph[u].add(v);
                graph[v].add(u);
            }
            dfs(0, -1, 0);
            if (max_cycle >= sq) {
                pn(2);
                pn(max_cycle);
                ArrayList<Integer> ans = new ArrayList<>();
                for (i = start; i != end; i = par[i])
                    ans.add(i);
                ans.add(end);
                for (int x : ans)
                    p(x + 1 + " ");
                return;
            }
            if (n < 100) {
                TreeSet<Integer> mis = MIS(n);
                pn(1);
                int c = 0;
                for (int x : mis) {
                    p(x + 1 + " ");
                    c++;
                    if (c == sq)
                        break;
                }
                return;
            }
            tarjan(0, -1);
            int root = -1;
            HashSet<Integer> hset = new HashSet<>();
            for (i = 0; i < n; i++) {
                int father = ob.find(i);
                for (int x : graph[i]) {
                    int lull = ob.find(x);
                    if (lull == father)
                        continue;
                    tset[lull].add(father);
                    tset[father].add(lull);
                }
                hset.add(father);
                if (father == i)
                    root = i;
            }

            dfs2(root, -1, 0);
            ArrayList<Integer> ans = new ArrayList<>();
            pn(1);
            TreeSet<Integer> good = new TreeSet<>();
            for (i = 0; i < n; i++)
                good.add(i);
            if (cnt[0] > cnt[1]) {
                int c = 0;
                for (int x : hset) {
                    if (dep[x] % 2 == 0) {
                        ans.add(x);
                        good.remove(x);
                        for (int y : graph[x]) {
                            good.remove(y);
                        }
                    }
                    if (ans.size() == sq)
                        break;
                }
            } else {
                int c = 0;
                for (int x : hset) {
                    if (dep[x] % 2 != 0) {
                        ans.add(x);
                        good.remove(x);
                        for (int y : graph[x]) {
                            good.remove(y);
                        }
                    }
                    if (ans.size() == sq)
                        break;
                }
            }
            while (ans.size() < sq) {
                int x = good.pollFirst();
                ans.add(x);
                for (int y : graph[x])
                    good.remove(y);
            }
            for (int x : ans)
                p(x + 1 + " ");
        }

        int ni() {
            return in.nextInt();
        }

        void pn(long zx) {
            out.println(zx);
        }

        void p(Object o) {
            out.print(o);
        }

        class DSU {
            int[] par;
            int[] sz;

            DSU(int n) {
                par = new int[n];
                sz = new int[n];
                int i = 0;
                for (i = 0; i < n; i++) {
                    par[i] = i;
                    sz[i] = 1;
                }
            }

            int find(int x) {
                if (par[x] != x)
                    return par[x] = find(par[x]);
                return par[x];
            }

            void unite(int x, int y) {
                int x_root = find(x);
                int y_root = find(y);
                if (x_root == y_root)
                    return;
                if (sz[x_root] <= sz[y_root]) {
                    par[x_root] = y_root;
                    sz[y_root] += sz[x_root];
                } else {
                    par[y_root] = x_root;
                    sz[x_root] += sz[y_root];
                }
            }

        }

        class Pair implements Comparable<Pair> {
            int x;
            int y;

            Pair(int x, int y) {
                this.x = x;
                this.y = y;
            }

            public int compareTo(Pair other) {
                if (this.x != other.x)
                    return this.x - other.x;
                return this.y - other.y;
            }

            public String toString() {
                return "(" + x + "," + y + ")";
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

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

        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}