# CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces

N, M ≤ 2e5

O( N + M ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;

int N, M, K;
vector< int > G[ MAXN ];

struct dsu{
vector< int > fa;
dsu( int size ){
fa = vector< int >( size );
for( int i = 0; i < size; ++i ){
fa[ i ] = i;
}
}
int find( int x ){
return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
bool unite( int x, int y ){
int a = find( x );
int b = find( y );
if( a == b ) return 0;
fa[ a ] = b;
return 1;
}
};

void dfs( int u, int fa, vector< int > &seq ){
seq.emplace_back( u );
for( int v : G[ u ] ){
if( v == fa ) continue;
dfs( v, u, seq );
seq.emplace_back( u );
}
}

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> M >> K;
dsu *uf = new dsu( N );
for( int i = 0; i < M; ++i ){
int x, y;
cin >> x >> y;
--x, --y;
if( uf->unite( x, y ) ){
G[ x ].emplace_back( y );
G[ y ].emplace_back( x );
}
}
}
{
vector< int > seq;
dfs( 0, -1, seq );
vector< vector< int > > ans( K );
for( int i = 0; i < seq.size(); ){
static int id = 0;
for( int j = 0; j < ( 2 * N + K - 1 ) / K and i < seq.size(); ++j, ++i ){
ans[ id ].emplace_back( seq[ i ] + 1 );
}
++id;
}
for( int i = 0; i < K; ++i ){
if( ans[ i ].empty() ){
cout << "1 1\n";
} else{
cout << ans[ i ].size() << " ";
for( int j = 0; j < ans[ i ].size(); ++j ){
cout << ans[ i ][ j ] << " \n"[ j + 1 == ans[ i ].size() ];
}
}
}
}
return 0;
}
```