#include <bits/stdc++.h>
using namespace std;
set<pair<int,int> > s;
vector<int> v[100005];
bool del[100005];
int deg[100005],occ[100005];
void remove(int node)
{
    if (del[node])
    return;
    s.erase({deg[node],node});
    del[node]=1;
    for (int u:v[node])
    {
        if (!del[u])
        {
            s.erase({deg[u],u});
            deg[u]--;
            s.insert({deg[u],u});
        }
    }
}
int main()
{
    int n,m,sq=1;
    scanf("%d%d",&n,&m);
    while (sq*sq<n)
    sq++;
    while (m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }
    for (int i=1;i<=n;i++)
    s.insert({deg[i],i});
    vector<int> ans;
    while (!s.empty())
    {
        auto p=*s.begin();
        s.erase(s.begin());
        if (p.first+1>=sq)
        {
            printf("2\n");
            vector<int> d({p.second});
            occ[p.second]=1;
            while (1)
            {
                pair<int,int> nex(1e9,0);
                for (int u:v[d.back()])
                {
                    if (!del[u])
                    nex=min(nex,make_pair(occ[u],u));
                }
                if (nex.first)
                {
                    printf("%d\n",(int)d.size()-nex.first+1);
                    for (int i=nex.first-1;i<d.size();i++)
                    printf("%d ",d[i]);
                    return 0;
                }
                d.push_back(nex.second);
                occ[nex.second]=d.size();
            }
        }
        ans.push_back(p.second);
        remove(p.second);
        for (int u:v[p.second])
        remove(u);
    }
    printf("1\n");
    for (int i=0;i<sq;i++)
    printf("%d ",ans[i]);
}