problem：

给定\(n\)个布尔型变量\(x_i\)以及他们之间的逻辑关系例如\((x_j\lor x_i) \land (\lnot x_p\lor x_q)……\)，求出一组合法解

solution：

显然每个点都有两种状态：真和假。这样我们可以把\(n\)个点拆分成\(2n\)个点，\(x\)和\(\lnot x\).

对于每一对关系\((i\lor j)\)，我们就可以\(\neg i\Longrightarrow j\)和\(\lnot j\Longrightarrow i\)这样连出两条边

那么现在变量\(x\)有四种连边的情况：

• \(x\)和\(\lnot x\)，此时之间没有边，随便取

• \(x\Longrightarrow \lnot x\)，此时\(x\)为假

• \(\lnot x\Longrightarrow x\)，此时\(x\)为真

• \(x\Longrightarrow \lnot x\)且\(\lnot x\Longrightarrow x\)，\(x\)又为真又为假，无解

那么如何求解的情况呢？？看看上面的第四种情况就可以联想到\(tarjan\)s缩点，如果\(x\)和\(\lnot x\)在同一个强联通分量中就无解

如果\(x\)所在的强连通分量的拓扑序在\(\lnot x\)所在的强连通分量之后\(x\)为真（并不会证明）。

另外拓扑序其实就是\(tarjan\)染色的逆序，这样我们只需要判断\(x\)的颜色\(<\)\(\lnot x\)的颜色就ok了

例题：

考虑对每个夫妇建两个点 \(x\),\(\lnot x\)，\(x\)表示妻子与新郎同侧，\(\lnot x\)则表示丈夫与新郎同侧。

那么对于一对关系\((a,b)\)，\(a\)向\(\lnot b\),\(b\)向\(\lnot a\)各连一条边，表示若\(a\)与新郎同侧，那么\(b\)不能与新郎同侧，也就是\(\lnot b\)一定要与新郎同侧，反之亦然。

输出时反过来，即若与新郎同侧的是妻子，那么与新娘同侧的（也就是需要输出的人）就是丈夫

（快读这东西就离谱）

code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int read(){
	int x = 1,a = 0;char ch = getchar();
	while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
	while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
	return x*a;
}

const int maxn = 4e5+10;

int n,m;

int getnum(int x){
	if (x > n) return x - n;
	return x + n;
}

struct node{
	int to,nxt;
}ed[maxn*2];

int head[maxn*2],tot;

void add(int u,int to){
	ed[++tot].to = to;
	ed[tot].nxt = head[u];
	head[u] = tot;
}

int col[maxn*2],top,dfn[maxn*2],low[maxn*2],color,cnt,st[maxn*2];

void tarjan(int x){
	dfn[x] = low[x] = ++cnt;
	st[++top] = x;
	for (int i = head[x];i;i = ed[i].nxt){
		int to = ed[i].to;
		if (!dfn[to]){
			tarjan(to);
			low[x] = min(low[x],low[to]);
		}
		else if (!col[to]) low[x] = min(low[x],dfn[to]);
	}
	if (dfn[x] == low[x]){
		++color;
		int y;
		while (y = st[top--]){
			col[y] = color;
			if (x == y) break;
		}
	}
}

bool flag;

void init(){
	memset(head,0,sizeof(head));
	memset(ed,0,sizeof(ed));
	memset(col,0,sizeof(st));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(st,0,sizeof(st));
	color = cnt = tot = top = 0;
	flag = true;
}

int main(){
	while (~scanf ("%d%d",&n,&m)&&(n+m) != 0){
		init();
		for (int i = 1;i <= m;i++){
			char op;
			int u ;scanf("%d",&u);scanf ("%c",&op);u++;
			if (op == 'h') u+=n;
			int v ;scanf("%d",&v);scanf ("%c",&op);v++;
			if (op == 'h') v+=n;
			add(u,getnum(v));
			add(v,getnum(u));
		}
		add(1,1+n);
		for (int i = 1;i <= 2*n;i++){
			if (!dfn[i]) tarjan(i);
		}
		for (int i = 1;i <= n&&flag;i++){
			if (col[i] == col[i+n]) flag = false;
		}
		if (!flag){printf("bad luck\n");continue;}
		for (int i = 2;i <= n;i++){
			if (col[i] > col[i+n]) printf("%dw ",i-1);
			else printf("%dh ",i-1);
		}
		puts("");
	}
	return 0;
}