#include #include #include using namespace std; typedef long long llong; pair< vector, vector > groups[100111]; int n,m; int A[100111]; bool blocked[100111]; int groupID[100111]; bool firstPart[100111]; llong gcd(llong a,llong b) { llong r; while(b != 0) { r = a % b; a = b; b = r; } return a; } void connect(int x,int y) { if (groupID[x] == groupID[y]) { if (firstPart[x] == firstPart[y]) { blocked[ groupID[x] ] = true; } return; } int G1 = groupID[x]; int G2 = groupID[y]; int sz1 = groups[G1].first.size() + groups[G1].second.size(); int sz2 = groups[G2].first.size() + groups[G2].second.size(); int i; if (sz1 < sz2) { connect(y,x); return; } blocked[G1] = blocked[G1] || blocked[G2]; if (firstPart[x] == firstPart[y]) { for (i=0;i