题意
解析
首先：dfs树找合法的环 性质：可以寻找到所有的环，我只需要看是否满足大于等于sq个点构成的简单环即可 满足即输出就行
然后：找出sq个点构成的最大独立集 构成合法环的最小环是：sq，侧面说明如果大于等于sq的环找不到，dfs树最大环<=sq-1的 也就是，我们只需要把深度%sq, 1：同一深度的顶点肯定无边 2：dfs最大环顶点数<=sq-1,距离sq-1的两个顶点，无边一定可以构成独立集 3：深度求余一定有一种情况满足，看上面图
题量链接
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define F first
#define S second
#define endl "\n"
#define eps 1e-6
#define base 131
#define lowbit(x) (x&(-x))
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define MAXN 0x7fffffff
#define INF 0x3f3f3f3f3f3f3f3f
#define ferma(a,b) pow(a,b-2)
#define mod(x) (x%mod+mod)%mod
#define pb push_back
#define decimal(x) cout << fixed << setprecision(x);
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define memset(a,b) memset(a,b,sizeof(a));
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std
;
template
<typename T
> inline T
fetch(){T ret
;cin
>> ret
;return ret
;}
template
<typename T
> inline vector
<T
> fetch_vec(int sz
){vector
<T
> ret(sz
);for(auto& it
: ret
)cin
>> it
;return ret
;}
template
<typename T
> inline void makeUnique(vector
<T
>& v
){sort(v
.begin(), v
.end());v
.erase(unique(v
.begin(), v
.end()), v
.end());}
void file()
{
#ifdef ONLINE_JUDGE
#else
freopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);
#endif
}
const int N
=2e5+5;
int deep
[N
],n
,m
,sq
;
bool vis
[N
];
stack
<int>sta
;
vector
<int>G
[N
],ans
[N
];
void dfs(int u
,int fat
)
{
vis
[u
]=true
;
deep
[u
]=deep
[fat
]+1;
sta
.push(u
);
ans
[deep
[u
]%(sq
-1)].pb(u
);
for(auto v
:G
[u
])
{
if(v
==fat
)
continue;
if(vis
[v
])
{
if(deep
[u
]-deep
[v
]+1>=sq
)
{
cout
<<2<<endl
;
cout
<<deep
[u
]-deep
[v
]+1<<endl
;
while(true
)
{
cout
<<sta
.top()<<" ";
if(sta
.top()==v
)
exit(0);
sta
.pop();
}
}
continue;
}
dfs(v
,u
);
}
sta
.pop();
}
signed main()
{
IOS
;
file();
cin
>>n
>>m
;
while(m
--)
{
int u
,v
;
cin
>>u
>>v
;
G
[u
].pb(v
);
G
[v
].pb(u
);
}
sq
=ceil(sqrt(n
));
dfs(1,0);
cout
<<1<<endl
;
for(int i
=0;i
<sq
;i
++)
{
if(ans
[i
].size()>=sq
)
{
for(auto it
:ans
[i
])
if(sq
)
cout
<<it
<<" ",sq
--;
return 0;
}
}
return 0;
}
