#include <bits/stdc++.h>
using namespace std;
vector< int > vis , id;
vector< vector< int > > graph;
void dfs( int node , int cnt)
{
vis[node] = 1;
id[node] = cnt;
for( int u : graph[node] )
{
if( !vis[u] )
dfs(u,cnt);
}
}
int main()
{
int nodes, edges;
cin >> nodes; // input number of nodes in graph
cin >> edges;
vis.resize(nodes+1, 0);
id.resize(nodes+1, 0);
graph.resize(nodes+1);
for( int i = 0 ; i < edges ; i++)
{
int u , v ;
cin >> u >> v;
graph[u].push_back(v); // we can use a pair of (v,cost) in case of weighted graph
graph[v].push_back(u); // if graph is Directed this line will be omitted.
}
int cnt = 1 ;
for( int i =1 ; i <= nodes ; i++)
{
if( !vis[i] )
{
dfs(i, cnt++);
}
}
while(true)
{
int a, b ;
cin >> a >> b;
if( id[a] == id[b] )
cout << "In same connected component\n";
else cout << "In different connected component\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvcjwgaW50ID4gdmlzICwgaWQ7CnZlY3RvcjwgdmVjdG9yPCBpbnQgPiA+IGdyYXBoOwp2b2lkIGRmcyggaW50IG5vZGUgLCBpbnQgY250KQp7Cgl2aXNbbm9kZV0gPSAxOwoJaWRbbm9kZV0gPSBjbnQ7Cglmb3IoIGludCB1IDogZ3JhcGhbbm9kZV0gKQoJewoJCWlmKCAhdmlzW3VdICkKCQkJZGZzKHUsY250KTsKCX0KfQppbnQgbWFpbigpCnsKCWludCBub2RlcywgZWRnZXM7CgljaW4gPj4gbm9kZXM7ICAgICAgLy8gaW5wdXQgbnVtYmVyIG9mIG5vZGVzIGluIGdyYXBoCgljaW4gPj4gZWRnZXM7Cgl2aXMucmVzaXplKG5vZGVzKzEsIDApOwoJaWQucmVzaXplKG5vZGVzKzEsIDApOwoJZ3JhcGgucmVzaXplKG5vZGVzKzEpOwoJZm9yKCBpbnQgaSA9IDAgOyBpIDwgZWRnZXMgOyBpKyspCgl7CgkJaW50IHUgLCB2IDsKCQljaW4gPj4gdSA+PiB2OwoJCWdyYXBoW3VdLnB1c2hfYmFjayh2KTsgICAgICAvLyB3ZSBjYW4gdXNlIGEgcGFpciBvZiAodixjb3N0KSBpbiBjYXNlIG9mIHdlaWdodGVkIGdyYXBoCgkJZ3JhcGhbdl0ucHVzaF9iYWNrKHUpOyAgICAgIC8vIGlmIGdyYXBoIGlzIERpcmVjdGVkIHRoaXMgbGluZSB3aWxsIGJlIG9taXR0ZWQuCgl9CgkKCWludCBjbnQgPSAxIDsKCWZvciggaW50IGkgPTEgOyBpIDw9IG5vZGVzIDsgaSsrKQoJewoJCWlmKCAhdmlzW2ldICkKCQl7CgkJCWRmcyhpLCBjbnQrKyk7CgkJfQoKCX0KCQoJd2hpbGUodHJ1ZSkKCXsKCQlpbnQgYSwgYiA7CgkJY2luID4+IGEgPj4gYjsKCQlpZiggaWRbYV0gPT0gaWRbYl0gKQoJCQljb3V0IDw8ICJJbiBzYW1lIGNvbm5lY3RlZCBjb21wb25lbnRcbiI7CgkJZWxzZSBjb3V0IDw8ICJJbiBkaWZmZXJlbnQgY29ubmVjdGVkIGNvbXBvbmVudFxuIjsKCX0KCglyZXR1cm4gMDsKfQ==