题意:n个点的联通图,一定能找到小于k的环或(k+1)/2个互不相邻点
#include<bits/stdc++.h>
using namespace std;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m, k;std::cin >> n >> m >> k;vector<vector<int>> e(n + 1);for(int i=0;i<m;i++){int x,y;cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}vector<int>dep(n+1,-1), fa(n+1,-1);function <void(int,int)> dfs = [&](int u, int p) {for(auto v:e[u]){if(v == p)continue;if(dep[v] == -1) {dep[v] = dep[u] + 1;fa[v] = u;dfs(v,u);}else if(dep[v] < dep[u] && dep[u]-dep[v] <= k -1) {cout<<2<<endl;cout<<dep[u]-dep[v]+1<<endl;for(int i=u;i!=fa[v];i=fa[i]){cout<<i<<" ";}cout<<endl;exit(0);}}};dep[1] = 0;dfs(1,-1);vector<int> c;int l = (k+1)/2;if(n - 1 == m){for(int x=0;x<2;x++){c.clear();for(int i=1;i<=n;i++){if((dep[i]&1)==x&&c.size()<l){c.push_back(i);}}if(c.size()==l)break;}}else {int u=1;while(dep[u] < 2*l -2) ++u;for(int i=0;i<l;i++,u=fa[fa[u]]){c.push_back(u);}}cout<< 1 << "\n";for(auto x:c)cout<<x<<" ";cout<<endl;return 0;
}