Ministers' Major Mess AC - Live Archive 4452

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stack>
#include <vector>
using namespace std;

const int MAXV = 210;
const int MAXE = 40010;

int n;
vector<int> adj[MAXV];
int num[MAXV], low[MAXV];
stack<int> s; bool inSt[MAXV];
int sccCnt, vCnt;
int scc[MAXV];

void dfsSCC(int u) {
    num[u]=low[u]=vCnt++;
    s.push(u); inSt[u]=true;

    for (int i=0; i<(int)adj[u].size(); i++) {
        int v=adj[u][i];

        if (num[v]==-1) {
            dfsSCC(v);
            low[u]=min(low[v],low[u]);
        }
        else
            if (inSt[v])
                low[u]=min(low[u],num[v]);
    }

    if (low[u]==num[u]) {
        int v=-1;

        do {
            v=s.top();
            s.pop();
            inSt[v]=false;
            scc[v]=sccCnt;
        } while (u!=v);

        sccCnt++;
    }
}

void tarjanSCC() {
    memset(num,-1,sizeof(num));
    memset(low,-1,sizeof(low));
    memset(inSt,0,sizeof(inSt));
    memset(scc,-1,sizeof(scc));
    sccCnt=0, vCnt=0;

    while (!s.empty())
        s.pop();

    for (int i=0; i<n; i++)
        if (num[i]==-1)
            dfsSCC(i);
}

int B,M;

inline int neg(int v) {
    if (v<B) return v+B;
    return v-B;
}

bool twosat() {
    tarjanSCC();

    for (int i=0; i<B; i++)
        if (scc[i]==scc[neg(i)])
            return false;
    return true;
}

void getVotes() {
    int k, vot[4];
    scanf("%d", &k);

    for (int i=0; i<k; i++) {
        char tmp;
        scanf("%d %c", &vot[i],&tmp);
        vot[i]--;
        if (tmp=='n') vot[i]=neg(vot[i]);
    }

    switch(k) {
        case 2:
        case 1:
            for (int i=0; i<k; i++)
                for (int j=0; j<k; j++)
                    adj[neg(vot[i])].push_back(vot[j]);
            break;
        case 3:
        case 4:
            for (int i=0; i<k; i++)
                for (int j=0; j<k; j++)
                    if (i!=j)
                        adj[neg(vot[i])].push_back(vot[j]);
            break;
    }
}

int _42=1;

int main() {
    while (1) {
        scanf("%d %d", &B,&M);
        if (!B && !M) break;

        n=2*B;
        for (int i=0; i<n; i++)
            adj[i].clear();

        for (int i=0; i<M; i++)
            getVotes();

        printf("Case %d: ", _42++);

        if (!twosat()) {
            printf("impossible\n");
            continue;
        }

        for (int i=0; i<B; i++) {
            bool t,f;
            adj[neg(i)].push_back(i);
            t=twosat();
            adj[neg(i)].pop_back();
            adj[i].push_back(neg(i));
            f=twosat();
            adj[i].pop_back();

            if (t&&f) printf("?");
            else
                if (t) printf("y");
                else printf("n");
        }

        printf("\n");
    }
    return 0;
}