CFR 742 E. Arpa’s overnight party and Mehrdad’s silent entering ( Bicoloring / Random )

Problem - E - Codeforces

O( N )

```int N;
vi A, B;

void init(){
cin >> N;
A = B = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ] >> B[ i ], --A[ i ], --B[ i ];
}

vvi G;
vi col;

void dfs( int u ){
for( int v : G[ u ] )
if( not col[ v ] )
col[ v ] = 3 - col[ u ],
dfs( v );
}

void preprocess(){
G = vvi( 2 * N );
for( int i = 0; i < N; ++i )
G[ A[ i ] ].emplace_back( B[ i ] ),
G[ B[ i ] ].emplace_back( A[ i ] ),
G[ 2 * i ].emplace_back( 2 * i + 1 ),
G[ 2 * i + 1 ].emplace_back( 2 * i );
col = vi( 2 * N );
for( int i = 0; i < 2 * N; ++i )
if( not col[ i ] )
col[ i ] = 1,
dfs( i );
}

void solve(){
for( int i = 0; i < N; ++i )
cout << col[ A[ i ] ] << " " << col[ B[ i ] ] << endl;
}
```

```int N;
vi A, B;

void init(){
cin >> N;
A = B = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ] >> B[ i ], --A[ i ], --B[ i ];
}

vi partner;
vi ans;

void preprocess(){
partner = vi( N * 2 );
ans = vi( N * 2 );
for( int i = 0; i < N; ++i )
partner[ A[ i ] ] = B[ i ],
partner[ B[ i ] ] = A[ i ],
ans[ A[ i ] ] = 1, ans[ B[ i ] ] = 2;
while( true ){
int modify = 0;
for( int i = 0; i < 2 * N; ++i ){
if( ans[ ( i - 1 + 2 * N ) % ( 2 * N ) ] == ans[ i ] and ans[ i ] == ans[ ( i + 1 ) % ( 2 * N ) ] ){
if( rand() & 1 )
swap( ans[ i ], ans[ partner[ i ] ] );
else
swap( ans[ ( i + 1 ) % ( 2 * N ) ], ans[ partner[ ( i + 1 ) % ( 2 * N ) ] ] );
modify = 1;
}
}
if( not modify )
break;
}
}

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