RA Duty Scheduler

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

typedef long long ll;
typedef pair<int, int> pii;

const int NMAX = 105;
const int INF = 2e9+5;

struct Edge {
    int dest, flow, rev;
};

int n, m, n1, n2;
vector<Edge> g[NMAX];
int d[NMAX];
int last[NMAX];
unordered_map<int, string> name;
int ans[NMAX][2];
int ans_cnt[NMAX];

void add_edge(int x, int y, int c) {
    g[x].push_back({ y, c, sz(g[y]) });
    g[y].push_back({ x, 0, sz(g[x]) - 1 });
}

void io() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
}

void read() {
    cin >> n1 >> n2;
    n = n1 + n2 + 2;
    string s;
    for (int i = 2, x, cnt; i <= n1 + 1; i++) {
        cin >> s >> cnt;
        name[i] = s;
        while (cnt--) {
            cin >> x;
            add_edge(i, x + n1 + 1, 1);
        }
    }
    for (int i = 2; i <= n1 + 1; i++)
        add_edge(1, i, 3);
    for (int i = n1 + 2; i < n; i++)
        add_edge(i, n, 2);
}

bool bfs() {
    memset(d, 0, sizeof(d));
    memset(last, 0, sizeof(last));

    queue<int> q;
    q.push(1);
    d[1] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == n) continue;
        for (auto &it : g[u]) {
            if (!d[it.dest] && it.flow > 0) {
                d[it.dest] = d[u] + 1;
                q.push(it.dest);
            }
        }
    }

    return d[n];
}

int dfs(int x, int flow) {
    if (x == n) return flow;

    for (; last[x] < sz(g[x]); last[x]++) {
        Edge &e = g[x][last[x]];
        if (e.flow > 0 && d[e.dest] == d[x] + 1) {
            if (int ret = dfs(e.dest, min(flow, e.flow))) {
                e.flow -= ret;
                g[e.dest][e.rev].flow += ret;
                return ret;
            }
        }
    }

    return 0;
}

int dinic(int x) {
    for (int i = 1; i <= n; i++) {
        for (auto &it : g[i]) {
            it.flow = 0;
            if (i == 1)
                it.flow = x;
            else if (it.dest == n)
                it.flow = 2;
            else if (i < it.dest)
                it.flow = 1;
        }
    }
    while (bfs()) {
        while (int flow = dfs(1, INF));
    }
    for (int i = 1; i <= n2; i++) ans_cnt[i] = 0;
    int ret = 0;
    for (int i = 2; i <= n1 + 1; i++) {
        for (auto &it : g[i]) {
            if (it.flow == 0 && it.dest != 1) {
                int idx = it.dest - n1 - 1;
                ans[idx][ans_cnt[idx]++] = i;
                ret++;
            }
        }
    }
    return ret;
}

signed main() {
    io();
    read();
    for (int i = 1; ; i++) {
        if (dinic(i) == 2 * n2) {
            cout << i << endl;
            break;
        }
    }
    for (int i = 1; i <= n2; i++)
        cout << "Day " << i << ": " << name[ans[i][0]] << ' ' << name[ans[i][1]] << endl;
    return 0;
}