//帶路徑壓縮的并查集擴(kuò)展形式
//用于動(dòng)態(tài)維護(hù)查詢friend-enemy型等價(jià)類
//維護(hù)和查詢復(fù)雜度略大于O(1)
//集合元素取值1..MAXN-1(注意0不能用!),默認(rèn)無關(guān)
#include <string.h>

#define MAXN 100000
#define sig(x) ((x)>0?1:-1)
#define abs(x) ((x)>0?(x):-(x))
#define _ufind_run(x) for(;p[t=abs(x)];x=sig(x)*p[abs(x)],p[t]=sig(p[t])*(p[abs(x)]?p[abs(x)]:abs(p[t])))
#define _run_both _ufind_run(i);_ufind_run(j)
#define _set_side(x) p[abs(i)]=sig(i)*(abs(i)==abs(j)?0:(x)*j)
#define _judge_side(x) (i==(x)*j&&i)

struct ufind{
	int p[MAXN],t;
	void init(){memset(p,0,sizeof(p));}
	int set_friend(int i,int j){_run_both;_set_side(1);return !_judge_side(-1);}
	int set_enemy(int i,int j){_run_both;_set_side(-1);return !_judge_side(1);}
	int is_friend(int i,int j){_run_both;return _judge_side(1);}
	int is_enemy(int i,int j){_run_both;return _judge_side(-1);}
};