按照题意, 分为新郎 和 新娘列, 然而新郎列出了gay佬, (新郎不介意出现百合)

此问题就是如何决策新郎那列座位问题

即新郎那列$a_i$这个位置坐第i对的新郎还是新娘的问题

设$a_i=0$代表这个位置坐新娘, 反之为新郎,

那直接并查集?

然而不行, 并查集解决的是无向的取值问题,

而这题关系是单向的(新娘列不关注有无通奸者)

那就只能2-sat了,

而这题比较特殊, 新郎列第0个位置必须为新郎(强制排除了一些答案)

根据2-sat逆序拓扑取值问题, 我们人为加边 (0, n-1) 强制 n-1 在 1拓扑序的后面

最后求完一组可行解, 是新郎列的, 我们还要把性别取反, 变成新娘列

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;

const int N = 2e3 + 5;

int n, m, _, k, h[N][N];
int dfn[N], low[N], df, st[N], top;
int c[N], scnt, opp[N];
bool inst[N];

void tarjan(int x) {
    dfn[x] = low[x] = ++df; inst[st[++top] = x] = 1;
    rep(y, 1, k) if (h[x][y])
        if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if (inst[y]) low[x] = min(low[x], dfn[y]);
    if (low[x] == dfn[x]) {
        ++scnt; int y;
        do inst[y = st[top--]] = 0, c[y] = scnt; while (y != x);
    }
}

bool check() {
    rep(i, 1, n) if (c[i] == c[i + n]) return puts("bad luck"), 1;
    return 0;
}

int main() {
    while (~scanf("%d%d", &n, &m), n || m) {
        k = n << 1; scnt = df = 0;
        rep(i, 1, n) opp[i] = i + n, opp[i + n] = i;
        rep(i, 1, k) dfn[i] = inst[i] = 0;
        rep(i, 1, k) rep(j, 1, k) h[i][j] = 0;
        h[1][n + 1] = 1;
        rep(i, 1, m) {
            int a, b; char s, t; scanf("%d%c %d%c", &a, &s, &b, &t);
            if (s == 'h') a += n;
            if (t == 'h') b += n;
            ++a, ++b, h[a][opp[b]] = h[b][opp[a]] = 1;
        }
        rep(i, 1, k) if (!dfn[i]) top = 0, tarjan(i);
        if (check()) continue;
        rep(i, 2, n) printf("%d%c ", i - 1, c[i] > c[i + n] ? 'w' : 'h'); puts("");
    }
    return 0;
}