Problem: Given a connected undirected graph with n vertices and an integer k, you have to either:

  * either find an independent set that has exactly ⌈k/2⌉ vertices.
  * or find a simple cycle of length at most k. 



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 that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.

Input

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

Each of the next m lines contains two 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 ⌈k/2⌉ 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 not exceeding n, the vertices in the desired cycle, in the order they appear in the cycle.

Examples

Input


4 4 3
1 2
2 3
3 4
4 1


Output


1
1 3 

Input


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


Output


2
3
2 3 4 

Input


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


Output


2
3
1 2 3 

Input


5 4 5
1 2
1 3
2 4
2 5


Output


1
1 4 5 

Note

In the first sample:

<image>

Notice that printing the independent set \{2,4\} is also OK, but printing the cycle 1-2-3-4 isn't, because its length must be at most 3.

In the second sample:

<image>

Notice that printing the independent set \{1,3\} or printing the cycle 2-1-4 is also OK.

In the third sample:

<image>

In the fourth sample:

<image>

Solution (in JAVA):

Solution:
import com.sun.org.apache.xerces.internal.impl.xs.util.XSObjectListImpl;
import org.omg.CORBA.INTERNAL;
import org.omg.CORBA.TRANSACTION_MODE;
import sun.nio.cs.ext.MacHebrew;
import sun.reflect.generics.tree.Tree;

import javax.management.MXBean;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


public class Main {

    public static void main(String[] args) {
    ScanReader scanner = new ScanReader(System.in);
//        Scanner scanner = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(scanner, out);
        out.close();
    }

    final static int MAXN = (int) (1e5 + 5);
    final static int MAXK = 505;
    static int N = 0;
    static int M = 0;
    static int K = 0;
    static int W = 0;
    static int H = 0;
    static int P = 0;
//    static int[][] A;
    static long[][] dp;
    static int[][] pre;
    static int curAns = Integer.MAX_VALUE;
    static long[] HASH;
    static long MOD = 1000000000 + 7;
    static List<Integer>[] G;
    static int[] PATH = new int[MAXN];
    static boolean CYCLE = false;
    static int[] MARK = new int[MAXN];
    static int[] VISPOS = new int[MAXN];

    static List<Integer> getPath(int from, int to) {
        List<Integer> ans = new ArrayList<>();
        for (int i = from; i < to; i++) {
            ans.add(PATH[i]);
        }

        return ans;
    }

    static List<Integer> dfs(int u, int p, int pathIndex) {
        if ((pathIndex + 1) / 2 >= K) {
            return getPath(0, pathIndex);
        }
        for (int v: G[u]) {
            if (VISPOS[v] < 0) {
                VISPOS[v] = pathIndex;
                PATH[pathIndex] = v;
                List<Integer> sp = dfs(v, u, pathIndex + 1);
                if (CYCLE) {
                    return sp;
                }
                VISPOS[v] = -1;
            } else {
                int cycleSize = pathIndex - VISPOS[v];
                if (cycleSize > 2 && cycleSize <= K) {
                    CYCLE = true;
                    return getPath(VISPOS[v], pathIndex);
                }
            }
        }

        return null;
    }

    static int[] COUNT = new int[2];
    static void dfs2(int u, int mark) {
        for (int v : G[u]) {
            if (MARK[v] == mark) {
                return;
            }
        }

        MARK[u] = mark;
        COUNT[mark] += 1;
        if (COUNT[mark] >= K) {
            return;
        }
        for (int v : G[u]) {
            if (MARK[v] < 0) {
                dfs2(v, mark ^ 1);
            }
        }
    }

    static void solve(ScanReader scanner, PrintWriter out) {
        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();

        G = new List[N+1];
        for (int i = 0; i <= N; i++) {
            G[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            G[u].add(v);
            G[v].add(u);
        }

        Arrays.fill(VISPOS, -1);
        VISPOS[1] = 0;
        PATH[0] = 1;
        List<Integer> path = dfs(1, -1, 1);

        if (CYCLE) {
            out.println(2);
            out.println(path.size());
            for (int i = 0; i < path.size(); i++) {
                if (i > 0) {
                    out.print(" ");
                }
                out.print(path.get(i));
            }
        } else {
            out.println(1);
            if (path != null && (path.size() + 1) / 2 >= K) {
                path = path.subList(0, K);
                for (int i = 0; i < K; i += 2) {
                    if (i > 0) {
                        out.print(" ");
                    }
                    out.print(path.get(i));
                }
            } else {
                K = K % 2 == 0 ? K / 2 : (K+1) / 2;
                Arrays.fill(MARK, -1);
                MARK[1] = 0;
                dfs2(1, 0);

                int mark = COUNT[0] >= COUNT[1] ? 0 : 1;
                boolean first = true;
                for (int i = 1; i <= N && K > 0; i++) {
                    if (MARK[i] == mark) {
                        if (!first) {
                            out.print(" ");
                        }
                        out.print(i);
                        first = false;
                        K--;
                    }
                }
            }
        }

        out.println();
    }


    static long pow(long a, long b) {
        if (a == 0) {
            return 0;
        }
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }

        long h = pow(a, b/2);
        long v = h * h;
        v %= MOD;

        if (b % 2 != 0) {
            v *= a;
            v %= MOD;
        }

        return v;
    }


    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int nextInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

class UnioinSet {
    private Map<Long, Long> parents = new HashMap<>();

    public Long find(Long u) {
        if (parents.getOrDefault(u, u).equals(u)) {
            return u;
        }

        return find(parents.get(u));
    }

    public void union(Long u, Long v) {
        Long pu = find(u);
        Long pv = find(v);

        parents.put(pu, pv);
    }
}

class Pair implements Comparable<Pair> {
    public Integer x;
    public Integer y;

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

//    public int toIndex(int base) {
//        return this.x * base + this.y;
//    }

    public List<Pair> neighbors() {
        List<Pair> ans = new ArrayList<>();
        ans.add(new Pair(this.x + 1, this.y));
        ans.add(new Pair(this.x - 1, this.y));
        ans.add(new Pair(this.x, this.y + 1));
        ans.add(new Pair(this.x, this.y - 1));

        return ans;
    }

    @Override
    public int compareTo(Pair o) {
        if (o.x != this.x) {
            return (int) (this.x - o.x);
        } else {
            return (int) (this.y - o.y);
        }
    }

    @Override
    public int hashCode() {
        Integer v = this.x * 100000 + this.y;
        return Integer.hashCode(v);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof Pair) {
            Pair op = (Pair) obj;
            return op.x.equals(this.x) && op.y.equals(this.y);
        }

        return false;
    }
}


class SegmentMaxTree {
    private int size;
    private int dsize;
    private long[] data;
    private long[] lazy;

    public void build(long[] data) {
        if (data == null || data.length <= 0) {
            return;
        }

        this.size = data.length;
        this.dsize = this.size * 4;
        this.data = new long[this.dsize];
        this.lazy = new long[this.dsize];
        this.build(1, 0, this.size-1, 0, this.size-1, data);
    }

    public void add(int fromIndex, long val) {
        this.add(1, 0, this.size-1, fromIndex, this.size-1, val);
    }

    public void add(int fromIndex, int toIndexInclusive, long val) {
        this.add(1, 0, this.size-1, fromIndex, toIndexInclusive, val);
    }

    public long getMax() {
        return this.getMax(1, 0, this.size-1, 0, this.size-1);
    }

    private void push(int index) {
        if (index < this.dsize && this.lazy[index] != 0) {
            long v = this.lazy[index];
            this.data[index] += v;
            this.lazy[index] = 0;
            int[] child = new int[] {index * 2, index * 2 + 1};
            for (int ci : child) {
                if (ci < this.dsize) {
                    this.lazy[ci] += v;
                }
            }
        }
    }

    private long build(int index, int nodel, int noder, int targetl, int targetr, long[] data) {
        if (nodel > targetr || noder < targetl || targetr < targetl) {
            return this.data[index];
        }

        if (targetl == targetr) {
            this.data[index] = data[targetl];
            return this.data[index];
        } else {
            int m = (nodel + noder) / 2;
            long a = this.build(index * 2, nodel, m, targetl, Math.min(m, targetr), data);
            long b = this.build(index * 2 + 1, m + 1, noder, Math.max(targetl, m+1), targetr, data);
            long c = Math.max(a, b);
            this.data[index] = c;

            return c;
        }
    }

    private long add(int index, int nodel, int noder, int targetl, int targetr, long val) {
        this.push(index);
        if (nodel > targetr || noder < targetl || targetl > targetr) {
            return this.data[index];
        }

        if (nodel == targetl && noder == targetr) {
            this.lazy[index] += val;
            return this.data[index] + this.lazy[index];
        } else {
            int m = (nodel + noder) / 2;
            long a = this.add(index * 2, nodel, m, targetl, Math.min(targetr, m), val);
            long b = this.add(index * 2 + 1, m + 1, noder, Math.max(targetl, m+1), targetr, val);
            long c = Math.max(a, b);
            this.data[index] = c;
            return c;
        }
    }

    private long getMax(int index, int nodel, int noder, int targetl, int targetr) {
        this.push(index);

        if (nodel > targetr || noder < targetl || targetr < targetl) {
            return this.data[index];
        } else if (nodel == targetl && noder == targetr) {
            return this.data[index];
        } else {
            int m = (nodel + noder) / 2;
            long a = this.getMax(index * 2, nodel, m, targetl, Math.min(m, targetr));
            long b = this.getMax(index * 2 + 1, m + 1, noder, Math.max(targetl, m+1), targetr);
            return Math.max(a, b);
        }
    }
}