Maximum Assignment Between Problems and Programmers

Given N problems and M programmers: Problem i has a set of tags tags[i]. Programmer j has a set of skills skills[j]. Problem i can be assigned to programmer j if their sets intersect. Each problem and each programmer can be assigned at most once. Find the maximum number of assignable problems and output one maximum-cardinality set of (problem_id, programmer_id) assignments. Both IDs are zero-based. Input N M <comma-separated tags of problem 0; - means empty> ... <tags of problem N-1> <comma-separated skills of programmer 0; - means empty> ... <skills of programmer M-1> Output Print the maximum matching size on the first line, followed by one problem_id programmer_id pair per line. Pair order is unrestricted. Constraints 1 <= N, M <= 2 * 10^4 The total number of tags and skills is at most 2 * 10^5. Tags are strings without spaces. Follow-ups: How can you avoid naively enumerating every problem-programmer pair? How would you construct candidate edges and compute matching in a distributed system? How would you maintain an approximate matching, or periodically recompute one, when problems and programmers dynamically arrive and leave in a stream? Example Input 2 2 a b a b Output 2 0 0 1 1