Problem Context

An island has two types of inhabitants: truth-tellers, who always tell the truth, and liars, who always lie. Each inhabitent has a unique integer identifier.

You are allowed n questions. Each question must be direcetd to one inhabitant, asking whether another inhabitant is a truth-teller. Based on the collected responses, you must determine each inhabitant's identity.

Input and Output Specifications

Input Format:

• Multiple test cases.
• First line per case: three non-negative integers n, p1, p2.
• n: total questions you can ask.
• p1: number of truth-tellers.
• p2: number of liars.
• Next n lines: each contains two integers x, y and a string ans.
• x: identifier of the inhabitant being asked.
• y: identifier of the inhabitant being inquired about.
• ans: "yes" if the answer is affirmative, "no" if negative.
• Input ends with a line containing "0 0 0".

Output Format:

• If the information suffices to determine every inhabitant's identity, output all truth-teller identifiers, one per line, followed by "end" on a new line.
• If the information is insufficient, output "no" on a single line.

Data Ranges:

• 1 ≤ x, y ≤ p1 + p2
• 0 ≤ n < 1000
• 0 ≤ p1, p2 < 300

Logical Analysis of Responses

There are four possible scenarios based on the types of the respondent and the subject:

• Truth-teller about truth-teller: answer is "yes".
• Truth-teller about liar: answer is "no".
• Liar about truth-teller: answer is "no".
• Liar about liar: answer is "yes".

Thus, the answer is "yes" if both are of the same type, and "no" if they are different. This allows us to model relationships using a disjoint-set union (DSU) with parity.

Disjoint-Set Union with Parity

We use a DSU where each node maintains a parity relative to its set's root.

• parent[i]: root of the set containing i.
• parity[i]: 0 if i has the same type as its parent, 1 if different.

Path Compression: When finding the root, update parity along the path.

Union Operation: Given x and y and their relation rel (0 for same type, 1 for different), merge their sets and update the parity of the new parent.

Dynamic Programming for Feasibility

After processing all responses, each connected component splits into two groups based on parity relative to the root. For component c:

• group[c][0]: count of nodes with parity 0 (same as root).
• group[c][1]: count of nodes with parity 1 (diffreent from root).

For each component, two assignments are possible:

1. Parity 0 group as truth-tellers, parity 1 as liars.
2. Parity 1 group as truth-tellers, parity 0 as liars.

We use dynamic programming to count the number of ways to assign p1 truth-tellers and p2 liars across all components.

Let dp[t][l] be the number of ways to assign t truth-tellers and l liars using processed components.

For each component c, update:

dp[t][l] += dp[t - group[c][0]][l - group[c][1]]  // assignment option 1
dp[t][l] += dp[t - group[c][1]][l - group[c][0]]  // assignment option 2

Only proceed if indices are non-negative.

Backtracking for Identity Determination

If dp[p1][p2] == 1, exactly one assignment exists. We backtrack through the DP table to determine which option was chosen for each component, thereby fixing the type of each node.

Then, for each inhabitant i, compare its parity with the decided type of its root to determine if it is a truth-teller, and output accordingly.

Implementation

#include <bits>
using namespace std;

const int MAX_N = 610; // Since p1 + p2 ≤ 600

int parent[MAX_N], parity[MAX_N];
int compSize[MAX_N][2];
int dp[MAX_N][MAX_N];
int assignment[MAX_N]; // 0: root type is truth-teller, 1: liar
vector<int> componentRoots;

int findRoot(int node) {
    if (parent[node] != node) {
        int root = findRoot(parent[node]);
        parity[node] ^= parity[parent[node]];
        parent[node] = root;
    }
    return parent[node];
}

void uniteSets(int x, int y, int sameType) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
        parity[rootY] = parity[x] ^ parity[y] ^ sameType;
    }
}

void backtrack(int truthNeeded, int liarNeeded, int compIdx) {
    if (truthNeeded == 0 && liarNeeded == 0) return;
    while (compIdx >= 0 && compSize[compIdx][0] == 0 && compSize[compIdx][1] == 0) compIdx--;
    
    int sizeSame = compSize[compIdx][0];
    int sizeDiff = compSize[compIdx][1];
    
    if (truthNeeded >= sizeSame && liarNeeded >= sizeDiff && 
        dp[truthNeeded - sizeSame][liarNeeded - sizeDiff] == 1) {
        assignment[compIdx] = 0;
        backtrack(truthNeeded - sizeSame, liarNeeded - sizeDiff, compIdx - 1);
    } else {
        assignment[compIdx] = 1;
        backtrack(truthNeeded - sizeDiff, liarNeeded - sizeSame, compIdx - 1);
    }
}

int main() {
    int queries, truthCount, liarCount;
    while (cin >> queries >> truthCount >> liarCount) {
        if (queries == 0 && truthCount == 0 && liarCount == 0) break;
        
        int totalPeople = truthCount + liarCount;
        for (int i = 1; i <= totalPeople; i++) {
            parent[i] = i;
            parity[i] = 0;
        }
        
        for (int i = 0; i < queries; i++) {
            int responder, subject;
            string response;
            cin >> responder >> subject >> response;
            int relation = (response == "yes") ? 0 : 1;
            uniteSets(responder, subject, relation);
        }
        
        memset(compSize, 0, sizeof compSize);
        componentRoots.clear();
        for (int person = 1; person <= totalPeople; person++) {
            int root = findRoot(person);
            if (root == person) {
                componentRoots.push_back(root);
            }
            compSize[root][parity[person]]++;
        }
        
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        int processedPeople = 0;
        for (int root : componentRoots) {
            int sameAsRoot = compSize[root][0];
            int diffFromRoot = compSize[root][1];
            processedPeople += sameAsRoot + diffFromRoot;
            for (int t = truthCount; t >= 0; t--) {
                for (int l = liarCount; l >= 0; l--) {
                    int total = t + l;
                    if (total > processedPeople) continue;
                    dp[t][l] = 0;
                    if (t >= sameAsRoot && l >= diffFromRoot) {
                        dp[t][l] += dp[t - sameAsRoot][l - diffFromRoot];
                    }
                    if (t >= diffFromRoot && l >= sameAsRoot) {
                        dp[t][l] += dp[t - diffFromRoot][l - sameAsRoot];
                    }
                }
            }
        }
        
        if (dp[truthCount][liarCount] == 1) {
            memset(assignment, -1, sizeof assignment);
            backtrack(truthCount, liarCount, componentRoots.size() - 1);
            for (int person = 1; person <= totalPeople; person++) {
                int root = findRoot(person);
                int rootIdx = find(componentRoots.begin(), componentRoots.end(), root) - componentRoots.begin();
                bool isTruthTeller = (parity[person] == assignment[rootIdx]);
                if (isTruthTeller) {
                    cout << person << "\n";
                }
            }
            cout << "end\n";
        } else {
            cout << "no\n";
        }
    }
    return 0;
}</int></bits>