53. Minimum Team to Cover Required Skills

Difficulty: hard · Bit Manipulation, Recursion

Problem

A project needs a list of required skills. There are `N` candidates, numbered from `0`, and each candidate has a set of skills. Choose the **smallest** team (fewest candidates) whose combined skills include every required skill. If several smallest teams exist, choose the one whose sorted list of indices is lexicographically smallest. If no team can cover all required skills, print `-1`.

Input

- Line 1: the required skills, separated by spaces. - Line 2: the integer `N`. - Next `N` lines: the skills of candidate `i`, separated by spaces (at least one skill each).

Output

Print the chosen candidate indices in increasing order, separated by single spaces, or `-1`.

Example 1

Input:
a b c d
4
a b
b c
c d
d
Output:
0 2

Explanation: No single candidate has all four skills. Among pairs in index order, (0, 1) lacks d, while (0, 2) covers a, b, c and d.

Example 2

Input:
a b c
3
a
b c
c
Output:
0 1

Explanation: Candidates 0 and 1 together cover a, b and c; no single candidate does.

Example 3

Input:
x y
2
x
x z
Output:
-1

Explanation: Nobody has skill y, so no team works: -1.

Constraints

- 1 <= number of required skills <= 16 (all distinct) - 1 <= N <= 16 - Each candidate has between 1 and 16 skills; skills are lowercase words of length 1 to 10 - Candidates may have skills that are not required

Solutions are judged against 3 sample and 9 hidden tests. Sign in to solve it · All problems