10 6
3h 7h
5w 3w
7h 6w
8w 3w
7h 3w
2w 5h
0 0

1h 2h 3w 4h 5h 6h 7h 8h 9h

题意：题目太绕了=-=有一对新人结婚。非常多对夫妇參加婚礼，共n对。如今安排全部人坐在一张桌子两边，且（1）每对夫妇不能坐在同一側（2）n对夫妇中有通奸关系（包含男男，男女，女女），有通奸关系的不能坐在新娘的对面。问是否存在可行的安排方案。若存在输出与新娘同側的人。

思路：注意新郎必须在还有一边，所以就要加一条新娘到新郎的边以满足情况。

代码：

#include <iostream>
#include <functional>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

#define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 1005;
const int MAXN = 100;
const int MAXM = 2010;
const int N = 1005;

struct Edge
{
    int to,next;
}edge[MAXM];

int n,m;
int tot,head[MAXN];
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];
bool Instack[MAXN];
int top,Index,scc;

void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

void Tarjan(int u)
{
    int v;
    Low[u]=DFN[u]=++Index;
    Instack[u]=true;
    Stack[top++]=u;
    for (int i=head[u];~i;i=edge[i].next)
    {
        v=edge[i].to;
        if (!DFN[v])
        {
            Tarjan(v);
            if (Low[u]>Low[v]) Low[u]=Low[v];
        }
        else if (Instack[v]&&Low[u]>DFN[v])
            Low[u]=DFN[v];
    }
    if (Low[u]==DFN[u])
    {
        scc++;
        do
        {
            v=Stack[--top];
            Instack[v]=false;
            Belong[v]=scc;
        }while (v!=u);
    }
    return ;
}

bool solvable(int n)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    top=Index=scc=0;
    for (int i=0;i<n;i++)
        if (!DFN[i])
            Tarjan(i);
    for (int i=0;i<n;i+=2)
    {
        if (Belong[i]==Belong[i^1])
            return false;
    }
    return true;
}

queue<int>q1;
vector<vector<int> >dag;
char color[MAXN];
int indeg[MAXN];
int cf[MAXN];

void solve(int n)
{
    dag.assign(scc+1,vector<int>());
    memset(indeg,0,sizeof(indeg));
    memset(color,0,sizeof(color));
    for (int u=0;u<n;u++)
    {
        for (int i=head[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
            if (Belong[u]!=Belong[v])
            {
                dag[Belong[v]].push_back(Belong[u]);
                indeg[Belong[u]]++;
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        cf[Belong[i]]=Belong[i^1];
        cf[Belong[i^1]]=Belong[i];
    }
    while (!q1.empty()) q1.pop();
    for (int i=1;i<=scc;i++)
        if (indeg[i]==0)
            q1.push(i);
    while (!q1.empty())
    {
        int u=q1.front();
        q1.pop();
        if (color[u]==0)
        {
            color[u]='R';
            color[cf[u]]='B';
        }
        int sz=dag[u].size();
        for (int i=0;i<sz;i++)
        {
            indeg[dag[u][i]]--;
            if (indeg[dag[u][i]]==0)
                q1.push(dag[u][i]);
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
    int i,j,a,b;
    char c1,c2;
    while (~scanf("%d%d",&n,&m))
    {
        if (n==0&&m==0) break;
        init();
        for (i=0;i<m;i++)
        {
            scanf("%d%c%d%c",&a,&c1,&b,&c2);
            if (c1=='w') a=2*a; else a=2*a+1;
            if (c2=='w') b=2*b; else b=2*b+1;
            addedge(a,b^1);
            addedge(b,a^1);
        }
        addedge(0,1);
        if (!solvable(2*n))
        {
            printf("bad luck\n");
            continue;
        }
        solve(2*n);
        for (i=1;i<n;i++)
        {
            if (i>1) printf(" ");
            if (color[Belong[2*i]]=='R') printf("%dh",i);
            else printf("%dw",i);
        }
        printf("\n");
    }
    return 0;
}