#include <bits/stdc++.h>
using namespace std;
int pos[100005];
vector<int> v[100005],col[100005],s;
vector<int> cyc;
bool dfs(int node)
{
    pos[node]=s.size();
    col[pos[node]%2].push_back(node);
    s.push_back(node);
    int low=-1;
    for (int u:v[node])
    {
        if (pos[u]!=-1 && pos[node]-pos[u]>1)
        low=max(low,pos[u]);
    }
    if (low!=-1)
    {
        for (int i=low;i<=pos[node];i++)
        cyc.push_back(s[i]);
        return 1;
    }
    for (int u:v[node])
    {
        if (pos[u]==-1)
        {
            if (dfs(u))
            return 1;
        }
    }
    s.pop_back();
    return 0;
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    while (m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(pos,-1,sizeof(pos));
    dfs(1);
    if (cyc.empty())
    {
        if (col[0].size()<col[1].size())
        swap(col[0],col[1]);
        printf("1\n");
        for (int i=0;i<(k+1)/2;i++)
        printf("%d ",col[0][i]);
    }
    else
    {
        if (cyc.size()<=k)
        {
            printf("2\n%d\n",cyc.size());
            for (int i:cyc)
            printf("%d ",i);
        }
        else
        {
            printf("1\n");
            for (int i=0;i<(k+1)/2;i++)
            printf("%d ",cyc[2*i]);
        }
    }
}