Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The bride and groom sit at one end, opposite each other, and the bride wears an elaborate headdress that keeps her from seeing people on the same side as her. It is considered bad luck to have a husband and wife seated on the same side of the table. Additionally, there are several pairs of people conducting adulterous relationships (both different-sex and same-sex relationships are possible), and it is bad luck for the bride to see both members of such a pair. Your job is to arrange people at the table so as to avoid any bad luck.

The input consists of a number of test cases, followed by a line containing 0 0. Each test case gives n, the number of couples, followed by the number of adulterous pairs, followed by the pairs, in the form "4h 2w" (husband from couple 4, wife from couple 2), or "10w 4w", or "3h 1h". Couples are numbered from 0 to n - 1 with the bride and groom being 0w and 0h.

For each case, output a single line containing a list of the people that should be seated on the same side as the bride. If there are several solutions, any one will do. If there is no solution, output a line containing "bad luck".

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 using namespace std;  9 const int mxn=100010; 10 char tp; 11 int n,m; 12 struct edge{int v,nxt;}e[mxn<<1]; 13 int hd[mxn],mct=1; 14 void add_edge(int u,int v){ 15     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct; 16     return; 17 } 18 int belone[mxn],cnt; 19 int st[mxn],top=0; 20 int low[mxn],dfn[mxn],dtime=0; 21 bool inst[mxn]; 22 void tarjan(int u){ 23     low[u]=dfn[u]=++dtime; 24     inst[u]=1; 25     st[++top]=u; 26     for(int i=hd[u];i;i=e[i].nxt){ 27         int v=e[i].v; 28         if(!dfn[v]){ 29             tarjan(v); 30             low[u]=min(low[u],low[v]); 31         } 32         else if(inst[v]) 33             {low[u]=min(low[u],dfn[v]);} 34     } 35     if(low[u]==dfn[u]){ 36         int v=-1;cnt++; 37         do{ 38             v=st[top--]; 39             inst[v]=0; 40             belone[v]=cnt; 41         } 42         while(v!=u); 43     } 44     return; 45 } 46 bool check(){//判断冲突  47     for(int i=0;i<n;i++){ 48         if(belone[i]==belone[i+n])return 0; 49     } 50     return 1; 51 } 52 // 53 int vis[mxn]; 54 vector<int>ve[mxn]; 55 int ind[mxn]; 56 int op[mxn]; 57 void solve(){ 58     memset(vis,-1,sizeof vis); 59     top=0; 60     // 61     memset(ind,0,sizeof ind); 62     memset(op,0,sizeof op); 63     for(int i=0;i<=cnt;i++)ve[i].clear(); 64     // 65     int ed=2*n; 66     for(int i=0;i<n;i++){//标记相对侧  67         op[belone[i]]=belone[i+n]; 68         op[belone[i+n]]=belone[i]; 69     } 70     for(int i=0;i<ed;i++) 71         for(int j=hd[i];j;j=e[j].nxt){ 72             int v=e[j].v; 73             if(belone[i]!=belone[v]){ 74                 ve[belone[i]].push_back(belone[v]); 75                 ind[belone[v]]++; 76             } 77         } 78     for(int i=1;i<=cnt;i++){ 79         if(!ind[i])st[++top]=i; 80     } 81     while(top){//拓扑排序染色  82         int u=st[top--]; 83         if(vis[u]==-1){ 84             vis[u]=0; 85             vis[op[u]]=1; 86         } 87         for(int i=0;i<ve[u].size();i++){ 88             int v=ve[u][i]; 89             ind[v]--; 90             if(!ind[v])st[++top]=v; 91         } 92     } 93     for(int i=1;i<ed;i++){ 94         if(i==n)continue; 95         if(vis[belone[i]]==0){ 96             if(i<n)printf("%d",i); 97             else printf("%d",i-n); 98             if(i<n)printf("w "); 99             else printf("h ");100         }101     }102     printf("\n");103     return;104 }105 void init(){106     mct=1;  cnt=0; dtime=0;107     memset(hd,0,sizeof hd);108     memset(belone,0,sizeof belone);109     memset(dfn,0,sizeof dfn);110     memset(low,0,sizeof low);111     return;112 }113 int main(){114 //    freopen("in.txt","r",stdin);115     int i,j,u,v;116     while(scanf("%d%d",&n,&m) && n && m){117         init();118         int ed=n*2;119         add_edge(0,0+n);120         char c1,c2;121         for(i=1;i<=m;i++){122             scanf("%d%c%d%c",&u,&c1,&v,&c2);123             if(c1==‘h‘ && c2==‘w‘){add_edge(u+n,v+n);add_edge(v,u);}124             if(c1==‘w‘ && c2==‘h‘){add_edge(u,v);add_edge(v+n,u+n);}125             if(c1==‘h‘ && c2==‘h‘){add_edge(u+n,v);add_edge(v+n,u);}126             if(c1==‘w‘ && c2==‘w‘){add_edge(u,v+n);add_edge(v,u+n);}127         }128         for(i=0;i<ed;i++){if(!dfn[i])tarjan(i);}129         if(!check()){130             printf("bad luck\n");131             continue;132         }133         solve();134     }135     return 0;136 }