#include <bits/stdc++.h>
using namespace std;
int pos[100005];
bool ex[100005];
vector<int> v[100005],col[100005],s;
vector<pair<int,int> > e;
deque<int> cyc;
void dfs(int node)
{
    pos[node]=s.size();
    col[pos[node]%2].push_back(node);
    s.push_back(node);
    for (int u:v[node])
    {
        if (pos[u]==-1)
        dfs(u);
        else if (cyc.empty() && pos[node]-pos[u]>1)
        {
            for (int i=pos[u];i<=pos[node];i++)
            {
                cyc.push_back(s[i]);
                ex[s[i]]=1;
            }
        }
    }
    s.pop_back();
}
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);
        e.push_back({a,b});
    }
    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
    {
        for (auto p:e)
        {
            if (ex[p.first] && ex[p.second] && abs(pos[p.first]-pos[p.second])!=1)
            {
                while (cyc.front()!=p.first && cyc.front()!=p.second)
                {
                    ex[cyc.front()]=0;
                    cyc.pop_front();
                }
                while (cyc.back()!=p.first && cyc.back()!=p.second)
                {
                    ex[cyc.back()]=0;
                    cyc.pop_back();
                }
            }
        }
        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]);
        }
    }
}