# CFR 228 E. The Road to Berland is Paved With Good Intentions ( 2SAT )

Problem - 228E - Codeforces

N ≤ 100

O( N + M )

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

const int MAXN = 100;

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

void dfs_topo( int u, vector< int > &vis, vector< int > &stk ){
for( int v : G[ u ] ){
if( vis[ v ] ) continue;
vis[ v ] = 1;
dfs_topo( v, vis, stk );
}
stk.emplace_back( u );
}

void dfs_ksrj( int u, vector< int > &scc, vector< vector< int > > &scc_vec, int cnt ){
for( int v : G[ u ] ){
if( scc[ v ] ) continue;
scc[ v ] = cnt;
scc_vec[ cnt ].emplace_back( v );
dfs_ksrj( v, scc, scc_vec, cnt );
}
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < M; ++i ){
int u, v, w; cin >> u >> v >> w; --u, --v;
if( w == 1 ){
G[ u ].emplace_back( v );
G[ N + u ].emplace_back( N + v );
G[ v ].emplace_back( u );
G[ N + v ].emplace_back( N + u );
} else{
G[ u ].emplace_back( N + v );
G[ N + u ].emplace_back( v );
G[ v ].emplace_back( N + u );
G[ N + v ].emplace_back( u );
}
}
int scc_cnt = 0;
vector< int > scc( 2 * N ), stk;
vector< vector< int > > scc_vec( 1 );
{ // kosaraju
vector< int > vis( 2 * N );
for( int i = 0; i < 2 * N; ++i ){
if( vis[ i ] ) continue;
vis[ i ] = 1;
dfs_topo( i, vis, stk );
}
for( int i = stk.size() - 1; i >= 0; --i ){
if( scc[ stk[ i ] ] ) continue;
scc[ stk[ i ] ] = ++scc_cnt;
scc_vec.emplace_back( vector< int >() );
scc_vec[ scc_cnt ].emplace_back( stk[ i ] );
dfs_ksrj( stk[ i ], scc, scc_vec, scc_cnt );
}
}
vector< int > sat( 2 * N );
for( int i = 0; i < 2 * N; ++i ){
if( sat[ i ] ) continue;
if( scc[ i ] == scc[ i < N ? i + N : i - N ] ){
cout << "Impossible\n";
exit( 0 );
}
sat[ scc[ i ] ] = 1;
sat[ scc[ ( i < N ? i + N : i - N ) ] ] = 2;
}
vector< int > ans;
for( int i = 1; i <= scc_cnt; ++i ){
if( sat[ i ] == 1 ) continue;
for( int j = 0; j < scc_vec[ i ].size(); ++j ){
if( N <= scc_vec[ i ][ j ] ) continue;
ans.emplace_back( scc_vec[ i ][ j ] + 1 );
}
}
cout << ans.size() << endl;
for( int i = 0; i < ans.size(); ++i ){
cout << ans[ i ] << " \n"[ i + 1 == ans.size() ];
}
return 0;
}
```