Problem Overview

Freight transportation protocols strictly prohibit placing mutually reactive or incompatible goods within the same shipping container. For example, storing oxidizers alongside flammable liquids poses a severe explosion risk. This computational task involves verifying multiple cargo manifests against a predefined list of prohibited item combinations to ensure each container meets safety compliance.

Input Specification

The initial line contains two integers: N (≤ 10,000), representing the total count of incompatible pairs, and M (≤ 100), denoting the number of container manifests to process.

The subsqeuent N lines each list a pair of conflicting item identifiers. Following this, M manifests are provided. Each manifest line follows the structure:

K ID_1 ID_2 ... ID_K

Here, K (≤ 1,000) specifies the quantity of goods in the container, while each ID represents a unique five-digit numerical identifier for a specific item. All value are separated by whitespace.

Output Specification

For every manifest evaluated, print Yes if the cargo configuration is safe. If any pair of incompatible items is detected within the container, output No. Each evaluation result must be printed on a new line.

Example Data

Input:

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

Output:

No
Yes
Yes

Optimized Solution Strategy

Performing pairwise comparisons between all items in a manifest against a large conflict registry results in excessive time complexity. A more efficient approach utilizes hash-based data structures for constant-time average lookups.

• Conflict Registry Construction: Utilize an unordered map to store adjacency relationships, where each key is an item identifier and the associated value is a dynamic array of its conflicting counterparts.
• Manifest Validation: Load each container's items into both a vector (for sequential iteration) and an unordered set (for O(1) membership verification). Iterate through the container's inventory, fetch the corresponding conflict list from the map, and cross-reference it against the set. If any conflict exists, immediately flag the manifest as unsafe.

This methodology reduces the per-manifest validation complexity to O(K + E), where K is the number of items in the container and E is the total number of conflict edges checked, guaranteeing performance well within standard execution limits.

Reference Implementation (C++)

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    // Optimize standard I/O operations for large datasets
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int conflict_pairs, manifest_count;
    if (!(cin >> conflict_pairs >> manifest_count)) return 0;

    // Adjacency structure mapping each item to its incompatible counterparts
    unordered_map<int, vector<int>> incompatibility_registry;

    for (int i = 0; i < conflict_pairs; ++i) {
        int cargo_a, cargo_b;
        cin >> cargo_a >> cargo_b;
        incompatibility_registry[cargo_a].push_back(cargo_b);
        incompatibility_registry[cargo_b].push_back(cargo_a);
    }

    for (int m = 0; m < manifest_count; ++m) {
        int shipment_size;
        cin >> shipment_size;

        vector<int> current_shipment(shipment_size);
        unordered_set<int> shipment_lookup;
        bool is_compliant = true;

        for (int idx = 0; idx < shipment_size; ++idx) {
            cin >> current_shipment[idx];
            shipment_lookup.insert(current_shipment[idx]);
        }

        // Verify against registered incompatibilities
        for (const int& item_id : current_shipment) {
            auto registry_it = incompatibility_registry.find(item_id);
            if (registry_it != incompatibility_registry.end()) {
                for (const int& restricted_item : registry_it->second) {
                    if (shipment_lookup.count(restricted_item)) {
                        is_compliant = false;
                        break;
                    }
                }
            }
            if (!is_compliant) break;
        }

        cout << (is_compliant ? "Yes\n" : "No\n");
    }

    return 0;
}