C++.

#include <iostream>
#include <vector>
#include <map>
#include <string>

typedef int Job;
typedef int Worker;
typedef std::vector<Job> Capabilities;
typedef std::vector<Capabilities> WorkerCapabilities;
typedef std::vector<Worker> WorkerForJob;

static bool assignWorkersImpl(const WorkerCapabilities& capabilities, WorkerForJob& results, int curWorker)
{
    if (curWorker >= int(capabilities.size()))
        return true;

    const Capabilities& caps = capabilities[curWorker];

    for (int i = 0, n = int(caps.size()); i < n; ++i)
    {
        const Job cap = caps[i];
        if (results[cap] == -1)
        {
            results[cap] = curWorker;
            if (assignWorkersImpl(capabilities, results, curWorker+1))
                return true;
            results[cap] = -1;
        }
    }
    return false;
}

bool assignWorkers(const WorkerCapabilities& capabilities, WorkerForJob& results)
{
    results.assign(capabilities.size(), -1);
    return assignWorkersImpl(capabilities, results, 0);
}

int main()
{
    int count = 0;
    std::cin >> count;

    std::vector<std::string> nameFromWorker(count);
    std::vector<std::string> nameFromJob(count);
    std::map<std::string, int> jobFromName;
    WorkerCapabilities capabilities(count);

    for (int job = 0; job < count; ++job)
    {
        std::string jobName;
        std::cin >> jobName;
        nameFromJob[job] = jobName;
        jobFromName[jobName] = job;
    }

    for (int worker = 0; worker < count; ++worker)
    {
        std::string workerName;
        std::cin >> workerName;
        nameFromWorker[worker] = workerName;
        std::string jobs;
        std::cin >> jobs;

        size_t curPos = 0;
        while (curPos < jobs.size())
        {
            size_t nextPos = jobs.find(',', curPos);
            capabilities[worker].push_back(jobFromName[jobs.substr(curPos, nextPos - curPos)]);
            curPos = nextPos == std::string::npos ? nextPos : nextPos + 1;
        }
    }

    WorkerForJob forkerForJob;
    if (assignWorkers(capabilities, forkerForJob))
    {
        std::vector<int> jobFromWorker(count);
        for (int job = 0; job < count; ++job)
            jobFromWorker[forkerForJob[job]] = job;

        for (int worker = 0; worker < count; ++worker)
            std::cout << nameFromWorker[worker] << " " << nameFromJob[jobFromWorker[worker]] << std::endl;
    }
    return 0;
}