# Yuki 416 旅行会社 ( Union Find, Smaller to Larger, Time Reverse )

No.416 旅行会社 - yukicoder

O( N lg N ) / O( N )

```int N, M, Q;
vp bridge;
vp destroy;

void init(){
cin >> N >> M >> Q;
bridge = vp( M );
for( int i = 0; i < M; ++i )
cin >> bridge[ i ].first >> bridge[ i ].second,
--bridge[ i ].first, --bridge[ i ].second;
destroy = vp( Q );
for( int i = 0; i < Q; ++i )
cin >> destroy[ i ].first >> destroy[ i ].second,
--destroy[ i ].first, --destroy[ i ].second;
}

set< pii > destroyed;

struct dsu{
vi fa;
vvi member;
dsu( int sz ){
fa = vi( sz );
member = vvi( sz );
for( int i = 0; i < sz; ++i )
fa[ i ] = i,
member[ i ].emplace_back( i );
}
int find( int x ){
return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
int unite( int x, int y ){
int a = find( x );
int b = find( y );
if( a == b )
return 0;
if( not ( member[ a ].size() >= member[ b ].size() ) )
swap( a, b );
for( int x : member[ b ] )
member[ a ].emplace_back( x );
member[ b ].clear(), member[ b ].shrink_to_fit();
fa[ b ] = a;
return 1;
}
int unite( int x, int y, vi &ans, int id ){
int a = find( x );
int b = find( y );
if( a == b )
return 0;
if( not ( member[ a ].size() >= member[ b ].size() ) )
swap( a, b );
if( b == find( 0 ) )
swap( a, b );
for( int x : member[ b ] ){
member[ a ].emplace_back( x );
if( a == find( 0 ) )
ans[ x ] = id;
}
member[ b ].clear(), member[ b ].shrink_to_fit();
fa[ b ] = a;
return 1;
}
int connected( int x, int y ){
int a = find( x );
int b = find( y );
return a == b;
}
} *uf;

vi ans;

void preprocess(){
for( int i = 0; i < Q; ++i )
destroyed.emplace( destroy[ i ] );
uf = new dsu( N );
for( int i = 0; i < M; ++i )
if( not destroyed.count( bridge[ i ] ) )
uf->unite( bridge[ i ].first, bridge[ i ].second ),
uf->unite( bridge[ i ].second, bridge[ i ].first );
ans = vi( N );
for( int i = 0; i < N; ++i )
if( uf->find( i ) == uf->find( 0 ) )
ans[ i ] = -1;
for( int i = Q - 1; i >= 0; --i )
uf->unite( destroy[ i ].first, destroy[ i ].second, ans, i + 1 );
}

void solve(){
for( int i = 1; i < N; ++i )
cout << ans[ i ] << endl;
}
```