In a project, you have a list of required skills req_skills, and a list of people.  The i-th person people[i] contains a list of skills that person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill.  We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].
Return any sufficient team of the smallest possible size, represented by the index of each person.
You may return the answer in any order.  It is guaranteed an answer exists.
 
Example 1:
Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]
Example 2:
Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

 
Constraints:

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
Every skill in people[i] is a skill in req_skills.
It is guaranteed a sufficient team exists.

Difficulty: interview

Starter code:

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        

Solutions:
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        

        def fulfill_skills(skills, person):
            remaining_skills = deque()
            for skill in skills:
                if skill not in people[person]:
                    remaining_skills.appendleft(skill)
            return remaining_skills

        # BFS by # of people
        # can reduce expansion by searching rarest skills first

        # map required skills to people
        # has_skill[\"java\"] == a list of people (int index into people) who have that skill
        has_skill = dict()
        for person, skills in enumerate(people):
            for skill in skills:
                experts = has_skill.get(skill, [])
                experts.append(person)
                has_skill[skill] = experts


        # sort skills by rarity
        rare_skills = [(len(people), skill)  for (skill, people) in list(has_skill.items())]
        rare_skills.sort()
        rare_skills = [skill for _, skill in rare_skills]


        for i in range(1, 17):
            # stack holds pairs:
            #   (skills, team)
            stack = [ (deque(rare_skills), []) ]
            while stack:
                skills, team = stack.pop()
                # print(skills, team)
                if not skills:
                    return team

                if len(team) + 1 > i:
                    continue
                # choose a member to fulfill next rarest skill
                skill = skills[0]
                for person in has_skill[skill]:
                    remaining_skills = fulfill_skills(skills, person)
                    stack.append( (remaining_skills, team + [person]) )
            # print(f\"i {i} failed\")

        return -1


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skillsMap = {s: i for i, s in enumerate(req_skills)}
        peopleSkills = collections.defaultdict(set)
        for i, p in enumerate(people):
            for s in p:
                peopleSkills[skillsMap[s]].add(i)
        n = len(req_skills)
        
        memo = {}
        res = []
        
        
        self.dfs(1 << n, memo, peopleSkills, res, n, people, skillsMap)
        return memo[1 << n]
    
    
    def dfs(self, state, memo, peopleSkills, res, n, people, skillsMap):
        # print(bin(state)[1:])
        if state == 2 ** (n+1) - 1:
            return []
        
        if state in memo:
            return memo[state]
        
        currState = list(bin(state)[3:])
        mini = float('inf')
        ans = []
        i = currState.index('0')
        for p in peopleSkills[i]:
            for s in people[p]:
                currState[skillsMap[s]] = '1'

            nextState = int('1' + ''.join(currState), 2)
            # print(bin(state), currState, p, nextState)
            temp = self.dfs(nextState, memo, peopleSkills, res, n, people, skillsMap)
            currState = list(bin(state)[3:])
            # print(p, state, nextState, temp)
            if len(temp) < mini:
                mini = len(temp)
                ans = [p] + temp
        # print(ans)
        memo[state] = ans
        return ans
                
        
        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        p_skills = [set() for _ in people]
        for i, p in enumerate(people):
            p_skills[i] = set(p)
        res = [0] * 17
        def dfs(idx=0, path=[], has=set()):
            nonlocal res
            if idx == len(req_skills):
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, path, has)
            elif len(path) + 1 < len(res):
                for i, p in enumerate(people):
                    if req_skills[idx] in p_skills[i]:
                        dfs(idx + 1, path + [i], has | p_skills[i])
        dfs()
        return res


\"\"\"
make a dictionary that is {skill  : people}
while still have skills
   find the rarest skill 
        option- iterate over the dictionary of skills (O(n_skills))
   for each person with the skill:
        add them, then combine them with the smallest Sufficient team from the remaining skills (recursion)
        pick the smallest of these
\"\"\"
from collections import defaultdict

class KeyToSetDict(object):
    def __init__():
        self.dict = {}
        self.sets = []
    
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skills_to_people = defaultdict(list)
        
        people = [set(p) for p in people]
        
        def add_person(i):
            for skill in people[i]:
                skills_to_people[skill].append(i)
                
        for i in range(len(people)):
            add_person(i)
        
        
        def remove_person(i):
            for skill in people[i]:
                skills_to_people[skill].remove(i)
        
        def inner(req_skills):
            if len(req_skills) == 0:
                return []
            
            # find (one of) the rarest skill
            rarest_skill = req_skills[0]
            count = len(skills_to_people[rarest_skill])
            for skill in req_skills[1:]:
                if len(skills_to_people[skill]) <= count:
                    rarest_skill = skill
                    count = len(skills_to_people[skill])

        
            result = []
            min_team_size = len(people)
            
            people_with_skill = skills_to_people[rarest_skill][:]
            for i in people_with_skill:
                remove_person(i)
                sub_req_skills = [x for x in req_skills if x not in set(people[i])]
                remaining_members = inner(sub_req_skills)
                if  len(remaining_members) + 1 <= min_team_size :
                    remaining_members.append(i)
                    result = remaining_members
                    min_team_size = len(result)
                add_person(i)
                    
                
            return result
        
        return inner(req_skills)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill2num = {}
        for i, skill in enumerate(req_skills):
            skill2num[skill] = i
        
        p2s = [0] * len(people)
        for i, p in enumerate(people):
            skills = 0
            for skill in p:
                if skill in skill2num:
                    skills += (1 << skill2num[skill])
            p2s[i] = skills
        
        N = len(req_skills)
        dp = [1000000000] * (1 << N)
        dp[0] = 0
        ans = [[] for i in range(1 << N)]
        
        for i in range(len(people)):
            dp2 = dp.copy()
            for skill in range(1 << N):
                new_skills = skill | p2s[i]
                if dp2[new_skills] > dp[skill] + 1:
                    dp2[new_skills] = dp[skill] + 1
                    ans[new_skills] = list(ans[skill])
                    ans[new_skills].append(i)
            dp = dp2
        
        return ans[(1 << N) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def convertToNum(people: List[str]) -> int:
            ans = 0
            for skill in people:
                ans |= 1 << (dic[skill])
            return ans
        
        dic = {v: i for i, v in enumerate(req_skills)}
        target = (1 << len(req_skills)) - 1
        dp = {v : [] for v in range(1, target+1)}
        for i, people_skill in enumerate(people):
            skill = convertToNum(people_skill)
            dp[skill] = [i]
            for key in list(dp.keys()):
                if key != skill and len(dp[key]) > 0 and i not in dp[key]:
                    new_skill = key | skill
                    if len(dp[new_skill]) > len(dp[key]) + 1 or len(dp[new_skill]) == 0:
                        temp = [v for v in dp[key]]
                        temp.append(i)
                        dp[new_skill] = temp
        
        return dp[target]
        
            
        


import heapq
from copy import deepcopy
from typing import List


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        person_bits = self.calculatePersonBits(req_skills, people)
        n = len(req_skills)
        dp = {
            0: set()
        }
        q = []
        heapq.heappush(q, 0)

        while len(q) > 0:
            index = heapq.heappop(q)
            for i in range(len(people)):
                if i not in dp[index]:
                    new_index = index | person_bits[i]
                    if new_index not in dp:
                        heapq.heappush(q, new_index)
                        dp[new_index] = deepcopy(dp[index])
                        dp[new_index].add(i)
                    elif len(dp[new_index]) > 1 + len(dp[index]):
                        dp[new_index] = deepcopy(dp[index])
                        dp[new_index].add(i)

        return list(dp[(2 ** n) - 1])

    def calculatePersonBits(self, req_skills, people):
        skills = {}
        i = 0
        for skill in req_skills:
            skills[skill] = 2 ** i
            i += 1

        result = []
        for person in people:
            total = 0
            for skill in person:
                total |= skills[skill]
            result.append(total)

        return result


from collections import deque

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # bit mask for people visited and bit mask for skills obtained
        # each bit mask (set), remember extra skills needed
        # remember every visited bit mask
        q = deque()
        skill_to_index = {}
        for i, skill in enumerate(req_skills):
            skill_to_index[skill] = i
            
        all_skills = (1 << len(req_skills)) - 1
        people_skills = [0] * len(people)
        dp = {}
        
        for i in range(len(people)):
            for skill in people[i]:
                people_skills[i] |= 1 << skill_to_index[skill]
            q.appendleft([1 << i, people_skills[i]])
            dp[people_skills[i]] = 1
        
        def count(bitmask):
            res = []
            for i in range(len(people)):
                if (1 << i) & bitmask:
                    res.append(i)
            return res
        
        while q:
            bitmask, skills = q.pop()
            
            if skills == all_skills:
                return count(bitmask)
            
            for i in range(len(people)):
                nbitmask = (1 << i) | bitmask
                nskills = people_skills[i] | skills
                if nskills not in dp or dp[nskills] > dp[skills] + 1:
                    dp[nskills] = dp[skills] + 1
                    q.appendleft([nbitmask, people_skills[i] | skills])
        
        return []


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def convertToNum(people: List[str]) -> int:
            ans = 0
            for skill in people:
                ans |= 1 << (dic[skill])
            return ans
        
        dic = {v: i for i, v in enumerate(req_skills)}
            
        dp = {v : [] for v in range(1, 1 << len(req_skills))}
        for i, people_skill in enumerate(people):
            skill = convertToNum(people_skill)
            dp[skill] = [i]
            for key in list(dp.keys()):
                if key != skill and len(dp[key]) > 0 and i not in dp[key]:
                    new_skill = key | skill
                    if len(dp[new_skill]) > len(dp[key]) + 1 or len(dp[new_skill]) == 0:
                        temp = [v for v in dp[key]]
                        temp.append(i)
                        dp[new_skill] = temp
        
        return dp[(1 << len(req_skills)) - 1]
        
            
        


class Solution:
    # dp
    # bit_manipulation
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # build a dict for skills
        N, skill_dict = len(req_skills), {}
        for i in range(N):
            skill_dict[req_skills[i]] = i
        # what is dp[i] = [], i is the bit expression of skills, value is a list of people with skills which i required
        dp = [list(range(len(people))) for _ in range(1 << N)]
        dp[0] = []

        # loop all people
        for i in range(len(people)):
            # get all skills of ith people
            skill = 0
            for s in people[i]:
                skill |= (1 << skill_dict[s])

            for k, v in enumerate(dp):
                # k is the skills, so new_skill is the new skills when add ith people to this list
                new_skill = k | skill
                # if skills increased and groups has less people, then updat dp
                if new_skill != k and len(v) + 1 < len(dp[new_skill]):
                    dp[new_skill] = v + [i]

        return dp[(1 << N) - 1]




class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # 为skills建立字典
        n = len(req_skills)
        d = dict()
        for i in range(n):
            d[req_skills[i]] = i
        # 所有状态
        dp = [list(range(len(people))) for _ in range(1 << n)]
        dp[0] = []
        # 遍历所有人
        for i in range(len(people)):
            # 求这个人的技能
            skill = 0
            for s in people[i]:
                skill |= (1 << d[s])
            for k, v in enumerate(dp):
                # 把这个人加入进来以后的团队技能
                new_skills = k | skill
                # 如果团队技能因此而增加 并且增加后的人数比新技能原来的人数少 则更新答案
                if new_skills != k and len(dp[new_skills]) > len(v) + 1:
                    dp[new_skills] = v + [i]
        return dp[(1 << n) - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skills = dict(zip(req_skills,list(range(len(req_skills)))))
        target = (1<<len(req_skills))-1
        for p in range(len(people)):
            temp = 0
            for s in people[p]:
                temp |= (1<<skills[s])
            people[p] = temp
            
        \"\"\"
        dp[i][j]: min people to have skills of j using first i people
        dp[0][0] = 0
        dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j]+1)
        
        \"\"\"
        
        dp = [[float(\"inf\"),[]] for _ in range(1+target)]
        dp[0] = (0,[])
        
        for r in range(len(people)):
            for c in range(target,-1,-1):
                #print(dp)
                #if dp[c][0] != float(\"inf\"):
                if dp[c][0]+1<dp[c|people[r]][0]:
                    dp[c|people[r]][0] = dp[c][0]+1
                    dp[c|people[r]][1] = dp[c][1]+[r]
        return dp[-1][1]
        
        
        
            
            

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        
        @functools.lru_cache(None)
        def helper(cur = 0):
            if cur == (1 << n) - 1:
                return []
            ans = math.inf
            res = []
            for i, p in enumerate(people):
                his_skill = 0
                for skill in p:
                    if skill in key:
                        his_skill |= 1 << key[skill]
                if his_skill | cur == cur:
                    continue
                temp = helper(cur | his_skill)
                if len(temp) + 1 < ans:
                    res = temp + [i]
                    ans = len(temp) + 1
            return res
        return helper()

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        # Firstly, convert all the sublists in people into sets for easier processing.
        for i, skills in enumerate(people):
            people[i] = set(skills)
        
        # Remove all skill sets that are subset of another skillset, by replacing the subset with an
        # empty set. We do this rather than completely removing, so that indexes aren't 
        # disrupted (which is a pain to have to sort out later).
        for i, i_skills in enumerate(people):
            for j, j_skills in enumerate(people):
                if i != j and i_skills.issubset(j_skills):
                    people[i] = set()
        
        # Now build up a dictionary of skills to the people who can perform them. The backtracking algorithm
        # will use this.
        skills_to_people = collections.defaultdict(set)
        for i, skills in enumerate(people):
            for skill in skills:
                skills_to_people[skill].add(i)
            people[i] = set(skills)
        
        # Keep track of some data used by the backtracking algorithm.
        self.unmet_skills = set(req_skills) # Backtracking will remove and readd skills here as needed.
        self.smallest_length = math.inf # Smallest team length so far.
        self.current_team = [] # Current team members.
        self.best_team = [] # Best team we've found, i,e, shortest team that covers skills/
        
\t\t# Here is the backtracking algorithm.
        def meet_skill(skill=0):
\t\t\t# Base case: All skills are met.
            if not self.unmet_skills:
\t\t\t\t# If the current team is smaller than the previous we found, update it.
                if self.smallest_length > len(self.current_team):
                    self.smallest_length = len(self.current_team)
                    self.best_team = self.current_team[::] # In Python, this makes a copy of a list.
                return # So that we don't carry out the rest of the algorithm.
                        
            # If this skill is already met, move onto the next one.
            if req_skills[skill] not in self.unmet_skills:
                return meet_skill(skill + 1)
\t\t\t\t# Note return is just to stop rest of code here running. Return values
\t\t\t\t# are not caught and used.
            
            # Otherwise, consider all who could meet the current skill.
            for i in skills_to_people[req_skills[skill]]:
                
\t\t\t\t# Add this person onto the team by updating the backtrading data.
                skills_added_by_person = people[i].intersection(self.unmet_skills)
                self.unmet_skills = self.unmet_skills - skills_added_by_person
                self.current_team.append(i)
                
\t\t\t\t# Do the recursive call to further build the team.
                meet_skill(skill + 1)
                
                # Backtrack by removing the person from the team again.
                self.current_team.pop()
                self.unmet_skills = self.unmet_skills.union(skills_added_by_person)
        
\t\t# Kick off the algorithm.
        meet_skill()        
        return self.best_team 


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skills = dict(zip(req_skills,list(range(len(req_skills)))))
        target = (1<<len(req_skills))-1
        for p in range(len(people)):
            temp = 0
            for s in people[p]:
                temp |= (1<<skills[s])
            people[p] = temp
            
        \"\"\"
        dp[i][j]: min people to have skills of j using first i people
        dp[0][0] = 0
        dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j]+1)
        
        \"\"\"
        
        dp = [[float(\"inf\"),[]] for _ in range(1+target)]
        dp[0] = (0,[])
        
        for r in range(len(people)):
            for c in range(target,-1,-1):
                #print(dp)
                if dp[c][0] != float(\"inf\"):
                    if dp[c][0]+1<dp[c|people[r]][0]:
                        dp[c|people[r]][0] = dp[c][0]+1
                        dp[c|people[r]][1] = dp[c][1]+[r]
        return dp[-1][1]
        
        
        
            
            

import functools
class Solution():
    def smallestSufficientTeam(self, req_skills, people):
        # 1:14
        # as we know skills are less  we can use bit to represent stage
        # lets use skills acquired statge to be 1
        # bits and dp question
        skills = dict()
        for i, v in enumerate(req_skills):
            skills[v] = i
        n = len(people)
        desiredskills = 2**len(skills)-1
        peopleskills=[]
        for p in people:
            mask=0
            for skill in p:
                mask|=1<<skills[skill]
            peopleskills.append(mask)
            
                
            
        @functools.lru_cache(None)
        def helper(i, teamskills):
            nonlocal n, desiredskills
            ans = float('inf')
            rlist = []
            if teamskills == desiredskills:
                return 0, None
            if i == n:
                return float('inf'), None
            # i will never reach n as answer exists
            # 2 options now
            # either we pick ith person or not
            # if we pick
            newteamskills = teamskills | peopleskills[i]
            
            # for skill in people[i]:
            #     skillpos = skills[skill]
            #     # set this bit to 1 in newpendingskills
            #     # and with zero
            #     newteamskills = newteamskills | (1 << skillpos)

            pickans, picklist = helper(i+1, newteamskills)
            pickans += 1

            if pickans < ans:
                ans = pickans
                rlist = [i]
                if picklist:
                    rlist.extend(picklist)
            pickans, picklist = helper(i+1, teamskills)
            if pickans < ans:
                ans = pickans
                if picklist:
                    rlist = picklist[:]
                else:
                    rlist = None
            return ans, rlist
        return helper(0, 0)[1]

#[Runtime: 2236 ms, faster than 10.62%] DP
#O(N * 2^R) N: number of people, R: number of skills
#f(i, S): the minimum people count to use first i people to fulfill state S
#state S is a binary set which is a combinations of skills
#f(N, all 1) = 0,  f(N, not all 1) = inf
#return f(-1, 0)
#f(i, S) = min( f(i+1, S) , 1+f(i+1, S + req_skill[i])
#WA: [\"gvp\",\"jgpzzicdvgxlfix\",\"kqcrfwerywbwi\",\"jzukdzrfgvdbrunw\",\"k\"]
#[[],[],[],[],[\"jgpzzicdvgxlfix\"],[\"jgpzzicdvgxlfix\",\"k\"],[\"jgpzzicdvgxlfix\",\"kqcrfwerywbwi\"],[\"gvp\"],[\"jzukdzrfgvdbrunw\"],[\"gvp\",\"kqcrfwerywbwi\"]]
from math import inf
def memorized(f):
    memo = {}
    def helper(*arg):
        if arg not in memo:
            memo[arg] = f(*arg)
        return memo[arg]
    return helper
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        N, MASK = len(people), (1 << len(req_skills))-1
        skill2id, child = {skill: i for i, skill in enumerate(req_skills)}, {}
        people = [sum(1 << skill2id[skill] for skill in skills) for skills in people]
        @memorized
        def dp(i: int, status: int) -> int:
            if i >= N:
                return 0 if status == MASK else inf
            not_choose, choose = dp(i+1, status), 1 + dp(i+1, status | people[i])
            if not_choose <= choose:
                child[(i, status)] = (i+1, status)
                return not_choose
            else:
                child[(i, status)] = (i+1, status | people[i])
                return choose
        i, mask, res = -1, 0, []
        dp(i, mask)
        #collect answer
        while mask < MASK:
            if child[(i, mask)] != (i+1, mask):
                res.append(i)
            i, mask = child[(i, mask)]
        return res

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        d = {}
        for i,s in enumerate(req_skills):
            d[s] = i
        
        p = []
        for s in people:
            c = 0
            for t in s:
                c |= 1 << d[t]
            p.append(c)
        # print(p)
        
        self.tar = 2**len(req_skills) -1
        self.r_len = len(people)
        self.r = []
        def dfs(l, t, cur):
            # print(l, t, cur, self.r)
            if cur == self.tar and len(l) < self.r_len:
                self.r_len = len(l)
                self.r = l.copy()
                return
            elif len(l) >= self.r_len or t > len(req_skills):
                return
            if cur & (1 << t):
                dfs(l, t+1, cur)
            for i,k in enumerate(p):
                if k & (1 << t) and not i in l:
                    tmp = cur
                    l.append(i)
                    cur |= k
                    dfs(l, t+1, cur)
                    cur = tmp
                    l.pop()
            
        dfs([], 0, 0)
        
        return self.r

import functools


class Solution():
    def smallestSufficientTeam(self, req_skills, people):
        # 1:14
        # as we know skills are less  we can use bit to represent stage
        # lets use skills acquired statge to be 1
        # bits and dp question
        skills = dict()
        for i, v in enumerate(req_skills):
            skills[v] = i
        n = len(people)
        desiredskills = 2**len(skills)-1
        @functools.lru_cache(None)
        def helper(i, teamskills):
            nonlocal n, desiredskills
            ans = float('inf')
            rlist = []
            if teamskills == desiredskills:
                return 0, None
            if i == n:
                return float('inf'), None
            # i will never reach n as answer exists
            # 2 options now
            # either we pick ith person or not
            # if we pick
            newteamskills = teamskills
            for skill in people[i]:
                skillpos = skills[skill]
                # set this bit to 1 in newpendingskills
                # and with zero
                newteamskills = newteamskills | (1 << skillpos)

            pickans, picklist = helper(i+1, newteamskills)
            pickans += 1

            if pickans < ans:
                ans = pickans
                rlist = [i]
                if picklist:
                    rlist.extend(picklist)
            pickans, picklist = helper(i+1, teamskills)
            if pickans < ans:
                ans = pickans
                if picklist:
                    rlist = picklist[:]
                else:
                    rlist = None
            return ans, rlist
        return helper(0, 0)[1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        peopleLen = len(people)
        skillsLen = len(req_skills)
        maskFull = (1 << skillsLen)-1
        newPeople = []
        for p in people:
            newPeople.append(set(p))
        
        dp = {}
        
        def findPeople(m0, i0):
            if m0 == maskFull:
                return []
            if i0 == peopleLen:
                return None
            if (m0, i0) in dp:
                return dp[(m0, i0)]
            nextM = m0
            for j in range(skillsLen):
                if m0 >> j & 1 == 1:
                    continue
                if req_skills[j] in newPeople[i0]:
                    nextM |= 1 <<j
            ans = None
            if nextM != m0:
                subAns = findPeople(nextM, i0+1)
                if subAns != None:
                    ans = subAns + [i0]
            subAns = findPeople(m0, i0+1)
            if ans == None or subAns != None and len(subAns) < len(ans):
                ans = subAns
            dp[(m0, i0)] = ans
            return ans
        
        return findPeople(0, 0)

#[Runtime: 1872 ms, faster than 12.67%] DP
#O(N * 2^R) N: number of people, R: number of skills
#f(i, S): the minimum people count to use first i people to fulfill state S
#state S is a binary set which is a combinations of skills
#f(N, all 1) = 0,  f(N, not all 1) = inf
#return f(-1, 0)
#f(i, S) = min( f(i+1, S) , 1+f(i+1, S + req_skill[i])
#WA: [\"gvp\",\"jgpzzicdvgxlfix\",\"kqcrfwerywbwi\",\"jzukdzrfgvdbrunw\",\"k\"]
#[[],[],[],[],[\"jgpzzicdvgxlfix\"],[\"jgpzzicdvgxlfix\",\"k\"],[\"jgpzzicdvgxlfix\",\"kqcrfwerywbwi\"],[\"gvp\"],[\"jzukdzrfgvdbrunw\"],[\"gvp\",\"kqcrfwerywbwi\"]]
from math import inf
from functools import reduce
from operator import or_
def memorized(f):
    memo = {}
    def helper(*arg):
        if arg not in memo:
            memo[arg] = f(*arg)
        return memo[arg]
    return helper
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        N, MASK = len(people), (1 << len(req_skills))-1
        skill2id, child = {skill: i for i, skill in enumerate(req_skills)}, {}
        people = [reduce(operator.or_, (1 << skill2id[skill] for skill in skills), 0) for skills in people]
        @memorized
        def dp(i: int, status: int) -> int:
            if i >= N:
                return 0 if status == MASK else inf
            not_choose, choose = dp(i+1, status), 1 + dp(i+1, status | people[i])
            if not_choose <= choose:
                child[(i, status)] = (i+1, status)
                return not_choose
            else:
                child[(i, status)] = (i+1, status | people[i])
                return choose
        i, mask, res = -1, 0, []
        dp(i, mask)
        #collect answer
        while mask < MASK:
            if child[(i, mask)] != (i+1, mask):
                res.append(i)
            i, mask = child[(i, mask)]
        return res

class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p: his_skill |= 1 << key[skill]
            if his_skill == 0 or his_skill in dp and len(dp[his_skill]) == 1: continue
            sn = copy.deepcopy(list(dp.items()))
            for skill_set, need in sn:
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        p_skills = [set() for _ in people]
        for i, p in enumerate(people):
            p_skills[i] = set(p)
        res = [0] * 17
        def dfs(idx=0, path=[], has=set()):
            nonlocal res
            if idx == len(req_skills):
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, path, has)
            elif len(path) + 1 < len(res):
                for i, p in enumerate(people):
                    if req_skills[idx] in p_skills[i]:
                        # intersection = has & p_skills[i]
                        # has |= p_skills[i]
                        # new = h
                        dfs(idx + 1, path + [i], has | p_skills[i])
                        # has -= {x for x in p_skills[i] if x not in intersection}
        dfs()
        return res


from collections import defaultdict
from functools import lru_cache

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        req_skills = set(req_skills)
        d = {}
        for i, x in enumerate(req_skills):
            d[x] = i
        
        @lru_cache(None)
        def dfs(state, idx):
            if state == 2 ** len(req_skills) - 1:
                return 0, []
            if idx == len(people):
                return float('inf'), []
            out = dfs(state, idx + 1)
            new_state = state
            for skill in people[idx]:
                new_state |= 1 << d[skill]
            new = dfs(new_state, idx + 1)
            if out[0] < new[0] + 1:
                return out
            return new[0] + 1, [idx] + new[1]
        
        return dfs(0, 0)[1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        p_skills = [set() for _ in people]
        for i, p in enumerate(people):
            p_skills[i] = set(p)
        # people.sort(key=lambda x: -len(set(x) & set(req_skills)))
        # # print(people)
        res = [0] * 17
        def dfs(idx=0, path=[], has=set()):
            nonlocal res
            if idx == len(req_skills):
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, path, has)
            elif len(path) + 1 < len(res):
                for i, p in enumerate(people):
                    if req_skills[idx] in p_skills[i]:
                        # intersection = has & p_skills[i]
                        # has |= p_skills[i]
                        # new = h
                        dfs(idx + 1, path + [i], has | p_skills[i])
                        # has -= {x for x in p_skills[i] if x not in intersection}
        dfs()
        return res


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        p_skills = [set() for _ in people]
        for i, p in enumerate(people):
            p_skills[i] = set(p)
        # people.sort(key=lambda x: -len(set(x) & set(req_skills)))
        # # print(people)
        res = [0] * 17
        def dfs(idx=0, path=[], has=set()):
            nonlocal res
            if idx == len(req_skills):
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, path, has)
            elif len(path) + 1 < len(res):
                for i, p in enumerate(people):
                    if req_skills[idx] in p_skills[i]:
                        intersection = has & p_skills[i]
                        has |= p_skills[i]
                        dfs(idx + 1, path + [i], has)
                        has -= {x for x in p_skills[i] if x not in intersection}
        dfs()
        return res


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        num_skills, team_queue = len(req_skills), collections.deque()
        bit_map, people_map = {req_skills[i]:i for i in range(num_skills)}, collections.defaultdict(list)
        for i, lst in enumerate(people):
            person_bit = 0
            for l in lst:
                person_bit = person_bit | (1<<bit_map[l])
            for l in lst:
                people_map[bit_map[l]].append((i, person_bit))
        
        team_queue.append((0, []))
        while team_queue:
            bits, team = team_queue.popleft()
            min_idx = 0
            while min_idx < num_skills and (bits & (1 << min_idx)):
                min_idx += 1
            if min_idx == num_skills:
                return team
            
            for p, person_bit in people_map[min_idx]:
                team_queue.append((bits | person_bit, team + [p]))
        
        return []

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        res = [''] * 17
        n = len(req_skills)
        def dfs(idx, has, path):
            nonlocal res
            if idx == n:
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, has, path)
            else:
                if len(path) + 1 < len(res):
                    for i, p in enumerate(people):
                        p = set(p)
                        if req_skills[idx] in p:
                            union = p & has
                            has |= p
                            dfs(idx + 1, has, path + [i])
                            has -= p
                            has |= union
        dfs(0, set(), [])
        return res
                        
        
        
        # n = len(req_skills)
        # key = {v: i for i, v in enumerate(req_skills)}
        # dp = {0: []}
        # for i, p in enumerate(people):
        #     his_skill = 0
        #     for skill in p:
        #         if skill in key:
        #             his_skill |= 1 << key[skill]
        #     for skill_set, need in list(dp.items()):
        #         with_him = skill_set | his_skill
        #         if with_him == skill_set: continue
        #         if with_him not in dp or len(dp[with_him]) > len(need) + 1:
        #             dp[with_him] = need + [i]
        # return dp[(1 << n) - 1]


from collections import defaultdict

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def backtrack(i, people_added, skills_added):
            nonlocal result
            if i == len(req_skills):
                result = people_added
            elif req_skills[i] in skills_added:
                backtrack(i+1, people_added, skills_added)
            else:
                if not result or len(people_added) < len(result) - 1:
                    for k in range(len(people)):
                        p = set(people[k])
                        if req_skills[i] in p:
                            union = p & skills_added
                            backtrack(i+1, people_added + [k], skills_added | p)
                            skills_added |= union
        result = []
        backtrack(0, [], set())
        return result


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        res = [''] * 17
        n = len(req_skills)
        def dfs(idx, has, path):
            nonlocal res
            if idx == n:
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, has, path)
            else:
                if len(path) + 1 < len(res):
                    for i, p in enumerate(people):
                        p = set(p)
                        if req_skills[idx] in p:
                            union = p & has
                            has |= p
                            dfs(idx + 1, has, path + [i])
                            has -= p
                            has |= union
        dfs(0, set(), [])
        return res
                        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        res = [''] * 17
        n = len(req_skills)
        def dfs(idx, has, path):
            nonlocal res
            if idx == n:
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, has, path)
            else:
                if len(path) + 1 < len(res):
                    for i, p in enumerate(people):
                        p = set(p)
                        if req_skills[idx] in p:
                            union = p & has
                            has |= p
                            dfs(idx + 1, has, path + [i])
                            has -= p
                            has |= union
        dfs(0, set(), [])
        return res

            
            
        

                        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        def fulfill_skills(skills, person):
            remaining_skills = deque()
            for skill in skills:
                if skill not in people[person]:
                    remaining_skills.appendleft(skill)
            return remaining_skills

        # BFS by # of people
        # can reduce expansion by searching rarest skills first

        # map required skills to people
        # has_skill[\"java\"] == a list of people (int index into people) who have that skill
        has_skill = dict()
        for person, skills in enumerate(people):
            for skill in skills:
                experts = has_skill.get(skill, [])
                experts.append(person)
                has_skill[skill] = experts


        # sort skills by rarity
        rare_skills = [(len(people), skill)  for (skill, people) in list(has_skill.items())]
        rare_skills.sort()
        rare_skills = [skill for _, skill in rare_skills]


        # queue holds pairs:
        #   (skills, team)
        q = deque()
        q.append( (deque(rare_skills), []) )
        while q:
            skills, team = q.popleft()
            print((skills, team))
            if not skills:
                return team

            # choose a member to fulfill next rarest skill
            skill = skills[0]
            for person in has_skill[skill]:
                remaining_skills = fulfill_skills(skills, person)
                q.append( (remaining_skills, team + [person]) )


        return -1


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            if his_skill == 0:
                continue
            if his_skill in dp and len(dp[his_skill]) == 1:
                continue
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        p_skills = [set() for _ in people]
        for i, p in enumerate(people):
            p_skills[i] = set(p)
        people.sort(key=lambda x: -len(set(x) & set(req_skills)))
        res = [0] * 17
        def dfs(idx=0, path=[], has=set()):
            nonlocal res
            if idx == len(req_skills):
                res = path
            elif req_skills[idx] in has:
                dfs(idx + 1, path, has)
            elif len(path) + 1 < len(res):
                for i, p in enumerate(people):
                    if req_skills[idx] in p_skills[i]:
                        intersection = has & p_skills[i]
                        has |= p_skills[i]
                        dfs(idx + 1, path + [i], has)
                        has -= {x for x in p_skills[i] if x not in intersection}
        dfs()
        return res


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        m = {val: i for i, val in enumerate(req_skills)}
        n = len(req_skills)
        skills = [reduce(lambda a, b: a + b, [1 << m[s] for s in row] or [0]) for row in people]
        final_state = reduce(lambda a, b: a + b, [1 << i for i in range(n)])
        dp = {0: []}
        for i, skill in enumerate(skills):
            for prev_state, team in dp.copy().items():
                new_state = prev_state | skill
                if new_state == prev_state: continue
                if new_state not in dp or len(team) + 1 < len(dp[new_state]):
                    dp[new_state] = team + [i]
        
        return dp[final_state] 

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        lrs = len(req_skills)
        skills = collections.defaultdict(list)
        peo_skills = []
        for i,skill in enumerate(people):
            for s in skill:
                skills[s].append(i)
        self.res = [0]*(lrs+1)       
        def dfs(idx,cover,path):
            if idx==lrs:
                self.res = path
            if idx>=lrs: return
            if req_skills[idx] in cover: 
                dfs(idx+1,cover,path)
            if len(path)+1<len(self.res):
                for p in skills[req_skills[idx]]:                 
                    p_s = set(people[p])
                    new_cover = cover|p_s
                    dfs(idx+1,new_cover,path+[p])
        dfs(0,set(),[])
        return self.res
                    

            
            
        

                        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        lrs = len(req_skills)
        skills = collections.defaultdict(list)
        peo_skills = []
        for i,skill in enumerate(people):
            for s in skill:
                skills[s].append(i)
        self.res = [0]*(lrs+1)       
        def dfs(idx,cover,path):
            if idx==lrs:
                self.res = path
            if idx>=lrs: return
            if req_skills[idx] in cover: 
                dfs(idx+1,cover,path)
            if len(path)+1<len(self.res):
                for p in skills[req_skills[idx]]:                 
                    p_s = set(people[p])
                    union = cover&p_s
                    cover |= p_s
                    dfs(idx+1,cover,path+[p])
                    cover -=p_s
                    cover |= union
        dfs(0,set(),[])
        return self.res
                    

            
            
        

                        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        dic = {x: i for i, x in enumerate(req_skills)}
        dp = {0:[]}
        for i, p in enumerate(people):
            his = 0
            for skill in p:
                his |= (1 << dic[skill])
            for s in list(dp.keys()):
                new = his | s
                if new == s:
                    continue
                if new not in dp or len(dp[new]) > len(dp[s]) + 1:
                    dp[new] = dp[s] + [i]
        return dp[(1 << len(req_skills)) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: tuple()}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for skill_set, need in list(dict(dp).items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him in dp and len(dp[with_him]) <= len(need) + 1: continue
                dp[with_him] = need + tuple([i])
        return dp[(1 << len(req_skills)) - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        from collections import defaultdict

        g = defaultdict(list)

        for i, skills in enumerate(people):
            for s in skills:
                g[s].append(i)

        memo = {}
        def helper(skills, group):
            if not skills:
                return set()
            
            if tuple(skills) in memo:
                return memo[tuple(skills)]
            
            
            new_group = None
            s = list(skills)[0]
            for ind in g[s]:
                if ind in group:
                    continue
                    
                comb = helper(skills - set(people[ind]), group | {ind}) | {ind}
                if not new_group or len(comb) < len(new_group):
                    new_group = comb
            # print(new_group)
            memo[tuple(skills)] = new_group
            return new_group

        return helper(set(req_skills), set())


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for skill_set, need in list(dict(dp).items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        key = {v : k for k, v in enumerate(req_skills)}
        dp = {0: []}
        for i, skills in enumerate(people):
            person_skill = 0
            for skill in skills:
                person_skill |= 1 << (key[skill])
            for skill_set, need in list(dict(dp).items()):
                nxt_skill_set = skill_set | person_skill
                if nxt_skill_set == skill_set: continue
                if nxt_skill_set in dp and len(dp[nxt_skill_set]) <= len(need) + 1: continue
                dp[nxt_skill_set] = need + [i]
        return dp[(1 << len(req_skills)) - 1]
        
        
        
        
        
        
        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
         
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            if his_skill == 0:
                continue
            # if his_skill in dp and len(dp[his_skill]) == 1:
            #     continue
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: 
                    continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]
                
            
            
     
        
        
        

        



class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
#         res = [''] * 17
#         n = len(req_skills)
#         def dfs(idx, has, path):
#             nonlocal res
#             if idx == n:
#                 res = path
#             elif req_skills[idx] in has:
#                 dfs(idx + 1, has, path)
#             else:
#                 if len(path) + 1 < len(res):
#                     for i, p in enumerate(people):
#                         p = set(p)
#                         if req_skills[idx] in p:
#                             union = p & has
#                             has |= p
#                             dfs(idx + 1, has, path + [i])
#                             has -= p
#                             has |= union
#         dfs(0, set(), [])
#         return res
                        
        
        
        n = len(req_skills)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p: his_skill |= 1 << key[skill]
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1: dp[with_him] = need + [i]
        return dp[(1 << n) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        countReqSkills, memo = len(req_skills), {0: []}
        skillToIndex = {v: i for i, v in enumerate(req_skills)}
        for i, ithSkills in enumerate(people):
            ithSkillsBitmap = 0
            for skill in ithSkills: ithSkillsBitmap |= 1 << skillToIndex[skill]
            for skillsBitmap, reqPpl in list(memo.items()):
                skillsBitmapAddI = skillsBitmap | ithSkillsBitmap
                if skillsBitmapAddI == skillsBitmap: continue
                if skillsBitmapAddI not in memo or len(reqPpl) + 1 < len(memo[skillsBitmapAddI]): memo[skillsBitmapAddI] = reqPpl + [i]
        return memo[(1 << countReqSkills) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him == skill_set: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]


# 5.05
class Solution:
        
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dp={0:[]}
        reqSkills={v:k for k,v in enumerate(req_skills)}
        for i,curSkills in enumerate(people):
            curMask=0
            for skill in curSkills:
                curMask|=1<<reqSkills[skill]
            for mask,team in list(dp.items()):
                m=mask|curMask
                if m==mask:
                    continue
                if m not in dp or 1+len(team)<len(dp[m]):
                    dp[m]=team+[i]
        return dp[(1<<len(req_skills))-1]
                
# class Solution:
#     def __init__(self):
#         self.minCnt=math.inf
#         self.minTeam=[]
        
#     def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
#         skills,team,skillsets,pids=set(req_skills),set(),set(),[]
#         people
#         for i,p in enumerate(people):
#             p=frozenset(p)
#             if not p or p in skillsets:
#                 continue
#             skillsets.add(p)
#             pids.append(i)
            
#         def dfs(skills, team):
#             if len(team)>self.minCnt:
#                 return
#             if not skills and len(team)<self.minCnt:
#                 self.minCnt=len(team)
#                 self.minTeam=list(team)
#             ps=sorted(((p,skills.intersection(people[p])) for p in pids if p not in team),\\
#                       key=lambda x:len(x[1]),reverse=True)
#             for p,curSkills in ps:
#                 if not curSkills:
#                     break
#                 team.add(p)
#                 skills-=curSkills
#                 dfs(skills,team)
#                 team.remove(p)
#                 skills.update(curSkills)
#         dfs(skills,team)
#         return self.minTeam


from functools import lru_cache
class Solution:
    def smallestSufficientTeam(self, l1: List[str], l2: List[List[str]]) -> List[int]:
        

        n = len(l1)
        l2 = [set(i) for i in l2]
        
        index = {}
        for i in range(n):
            index[l1[i]] = i

        @lru_cache(None)
        def dp(mask, i):
            # if mask == 2 ** n - 1:return set()
            if i == n:
                return set() if mask == 2 ** n - 1 else set(range(len(l2)))
            
                        
            curr = set(range(len(l2)))
            
            if (mask >> i) & 1 == 1:
                temp = dp(mask, i + 1)
                if len(temp) < len(curr):curr = temp
            
            
            for ind, j in enumerate(l2):
                if l1[i] in j:
                    masknow = mask
                    for k in j:
                        if (masknow >> index[k]) & 1 == 0:
                            masknow += (1 << index[k])
                    temp = set([ind]) | dp(masknow, i + 1)
                    
                    if len(temp) < len(curr):curr = temp
            return curr
                        
        return sorted(list(dp(0, 0)))


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        skill_to_idx = {s: idx for idx, s in enumerate(req_skills)}
        
        skills = []
        for p in people:
            mask = 0
            for s in p:
                mask |= (1 << skill_to_idx[s])
            skills.append(mask)

            
        dp = {0:[]}
        for i in range(len(people)):
            tmp = dp.copy()
            for s, p in list(dp.items()):
                ns = s | skills[i]
                if ns not in tmp or len(p) + 1 < len(tmp[ns]):
                    tmp[ns] = p + [i]
            dp = tmp
            
        return dp[(1 << n ) - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # Use dp and use bit to map the skill
        mapping = {v:i for i,v in enumerate(req_skills)}
        record = {0:[]}
        for i, p in enumerate(people):
            skills = 0
            for s in p:
                if s in mapping:
                    skills |= 1<<mapping[s]
            for v,l in list(record.items()):
                withThis = v|skills
                if withThis == v:continue
                if withThis not in record or len(record[withThis]) > len(l)+1:
                    record[withThis] = l+[i]
        return record[(1<<len(req_skills))-1]
            
        
        
        
#         skills = set(req_skills)
#         res = []
#         def recursive(index,team):
#             if index == len(people):
#                 if set(got.keys()) == skills:res.append(team)
#             else:
#                 for i in range(index,len(people)):
#                     for s in people[i]:
#                         got[s] += 1
#                     recursive(i+1,team+[i])
#                     for s in people[i]:
#                         got[s] -= 1
#                         if got[s] == 0:
#                             del got[s]
                        
#         got = collections.defaultdict(int)
#         recursive(0,[])
#         res.sort(key=lambda x:len(x))
#         return res[0]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dp = {
            0: []
        }
        
        skill_to_index = {skill: i for i, skill in enumerate(req_skills)}
        for i, skills in enumerate(people):
            mask = 0
            for skill in skills:
                mask |= 1 << (skill_to_index[skill])
            keys = list(dp.keys())
            for filled_req in keys:
                new_filled_req = filled_req | mask
                if (new_filled_req not in dp) or (len(dp[new_filled_req]) > len(dp[filled_req]) + 1):
                    dp[new_filled_req] = dp[filled_req] + [i]
        return dp[(1 << len(req_skills))-1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skillIdx = {}
        dp = {}
        dp[0] = []
        
        for idx, skill in enumerate(req_skills):
            skillIdx[skill] = idx
        
        for idx, personSkills in enumerate(people):
            skillBits = 0
            for skill in personSkills:
                skillBits |= 1 << skillIdx[skill]
            for prevSkills, _ in list(dp.items()):
                newSkills = prevSkills | skillBits
                if newSkills == prevSkills:
                    continue
                if newSkills not in dp or len(dp[newSkills]) > len(dp[prevSkills]) + 1:
                    dp[newSkills] = dp[prevSkills] + [idx]
        
        return dp[(1 << len(req_skills)) - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_idx = {s: i for i, s in enumerate(req_skills)}
        n = len(req_skills)
        
        def encode(p):
            res = 0
            for sk in p:
                res |= 1 << skill_idx[sk]
            return res
        
        people_code = [encode(p) for p in people]
        target = (1 << n) - 1
        people_arr = 0
        m = len(people)
        
        
        covers = {0: []}
        for i, pcode in enumerate(people_code):
            for code, people_arr in list(covers.copy().items()):
                new_code = pcode | code
                
                if new_code == code or (new_code in covers and len(people_arr) >= len(covers[new_code])):
                    continue
                covers[new_code] = people_arr + [i]
        return covers[target]
                    
            
        
                    
        
                
            


class Solution:
    
    def rec(self, rs, rdic, people, ret, rett, unis):
        if len(set(unis)) == len(rs):
            if len(ret) < len(rett):
                return ret
            
        if len(ret) >= len(rett):
            return rett
        
        for r,v in list(rs.items()):
            if r not in set(unis):
                for p in rdic[r]:
                    rett = self.rec(rs, rdic, people, ret + [p], rett, unis + people[p])
                break
        return rett
                
        
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        rdic = {}
        rs = {}
        for r in req_skills:
            rdic[r] = []
            rs[r] = 0
        
        for i in range(len(people)):
            for r in range(len(people[i])):
                rdic[people[i][r]].append(i)
        
        rett = [i for i in range(len(people))]
        return self.rec(rs, rdic, people, [], rett, [])
        
        
            
        
        
        
        


class Solution:
    from collections import defaultdict
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic={req_skills[rs]:2**rs for rs in range(len(req_skills))}
        dp=(defaultdict(list))
        m_pp=[]
        for pp in range(len(people)):
            # temp=dp.copy()
            res=0
            for itr_pp in people[pp]:
                res+=dic[itr_pp]
            # print(res, people[pp])
            if res!=0:
                keys=list(dp.keys())
                dp[res]=[pp]
                for j in keys:
                    if len(dp[j])>0:
                        sum_=j|res
                        if len(dp[sum_])==0 or len(dp[sum_])>len(dp[j]+[pp]):
                                dp[sum_]=dp[j]+[pp]
                # dp=temp
        # def recur(idx,val,res):
        #     if len(dp[val])==0 or len(dp[val])>len(res):
        #         dp[val]=res
        #     if len(dp[val])<len(res):return
        #     if idx==len(m_pp):return
        #     for i in range(idx,len(m_pp)):
        #         # print(res,[i])
        #         if m_pp[i]==0:continue
        #         recur(i+1,val|m_pp[i],res+[i])
        # recur(0,0,[])
        # print(dp)
        return dp[2**len(req_skills)-1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        hm = {v:i for i, v in enumerate(req_skills)}
        dp = {0:[]}
        
        for i, skills in enumerate(people):
            p_skills = 0
            for sk in skills:
                if sk in hm:
                    p_skills |= 1<<(hm[sk])
                    
            for sks, need in list(dp.items()):
                now = sks|p_skills
                
                if now not in dp or len(dp[now])>len(need)+1:
                    dp[now] = need+[i]
                    
        return dp[(1<<len(req_skills))-1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        lrs = len(req_skills)
        skills = collections.defaultdict(list)
        peo_skills = []
        for i,skill in enumerate(people):
            for s in skill:
                skills[s].append(i)
        self.res = [0]*(lrs+1)       
        def dfs(idx,cover,path):
            if idx==lrs:
                self.res = path
            elif idx>=lrs: return
            elif req_skills[idx] in cover: 
                dfs(idx+1,cover,path)
            else:
                if len(path)+1<len(self.res):
                    for p in skills[req_skills[idx]]:                 
                        p_s = set(people[p])
                        union = cover&p_s
                        cover |= p_s
                        dfs(idx+1,cover,path+[p])
                        cover -=p_s
                        cover |= union
        dfs(0,set(),[])
        return self.res
                    

            
            
        

                        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def convertToNum(people: List[str]) -> int:
            ans = 0
            for skill in people:
                ans |= 1 << (dic[skill])
            return ans
        
        dic = {v: i for i, v in enumerate(req_skills)}
        target = (1 << len(req_skills)) - 1
        dp = dict()
        for i, people_skill in enumerate(people):
            skill = convertToNum(people_skill)
            temp = dict()
            temp[skill] = [i]
            for key in list(dp.keys()):
                if key != skill:
                    new_skill = key | skill
                    if new_skill not in list(dp.keys()) or len(dp[new_skill]) > len(dp[key]) + 1:
                        t = [v for v in dp[key]]
                        t.append(i)
                        if new_skill not in list(temp.keys()) or len(temp[new_skill]) > len(t):
                            temp[new_skill] = t
                                
            dp.update(temp)
        
        return dp[target]
        
            
        


class Solution:
    from collections import defaultdict
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic={req_skills[rs]:2**rs for rs in range(len(req_skills))}
        dp=(defaultdict(list))
        m_pp=[]
        for pp in range(len(people)):
            # temp=dp.copy()
            res=0
            for itr_pp in people[pp]:
                res+=dic[itr_pp]
            # print(res, people[pp])
            if res!=0:
                dp[res]=[pp]
                keys=list(dp.keys())
                for j in keys:
                    if len(dp[j])>0:
                        sum_=j|res
                        if len(dp[sum_])==0 or len(dp[sum_])>len(dp[j]+[pp]):
                                dp[sum_]=dp[j]+[pp]
                # dp=temp
        # def recur(idx,val,res):
        #     if len(dp[val])==0 or len(dp[val])>len(res):
        #         dp[val]=res
        #     if len(dp[val])<len(res):return
        #     if idx==len(m_pp):return
        #     for i in range(idx,len(m_pp)):
        #         # print(res,[i])
        #         if m_pp[i]==0:continue
        #         recur(i+1,val|m_pp[i],res+[i])
        # recur(0,0,[])
        # print(dp)
        return dp[2**len(req_skills)-1]


class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        return dp[(1 << n) - 1]


#skillsets[skillset] = team, is a sufficient team to cover the skillset.
#For each people, update skillsets with all current combinations in skillsets.
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skillid = {skill: i for i, skill in enumerate(req_skills)}
        skillsets = {0: []}
        for i, p in enumerate(people):
            #create people[i]'s skill mask
            skillmask = 0
            for skill in p:
                if skill in skillid:
                    skillmask |= (1 << skillid[skill])
            #combine
            current_skillsets = list(skillsets.keys())
            for skillset in current_skillsets:
                within_i = skillset | skillmask
                if within_i not in skillsets or len(skillsets[within_i]) > len(skillsets[skillset])+1:
                    skillsets[within_i] = skillsets[skillset] + [i]
        c, mult = 0, 1
        for i in range(len(req_skills)):
            c += mult
            mult *= 2
        return skillsets[c]


class Solution:
    from collections import defaultdict
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic={req_skills[rs]:2**rs for rs in range(len(req_skills))}
        dp=defaultdict(list)
        m_pp=[]
        for pp in range(len(people)):
            temp=dp.copy()
            res=0
            for itr_pp in people[pp]:
                res+=dic[itr_pp]
            # print(res, people[pp])
            if res!=0:
                temp[res]=[pp]
                for j,v in list(dp.items()):
                    if len(temp[j])>0:
                        sum_=j|res
                        if len(temp[sum_])==0 or len(temp[sum_])>len(temp[j]+[pp]):
                                temp[sum_]=temp[j]+[pp]
                dp=temp
        # def recur(idx,val,res):
        #     if len(dp[val])==0 or len(dp[val])>len(res):
        #         dp[val]=res
        #     if len(dp[val])<len(res):return
        #     if idx==len(m_pp):return
        #     for i in range(idx,len(m_pp)):
        #         # print(res,[i])
        #         if m_pp[i]==0:continue
        #         recur(i+1,val|m_pp[i],res+[i])
        # recur(0,0,[])
        # print(dp)
        return dp[2**len(req_skills)-1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        dic = {v: i for i, v in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            cur_skill = 0
            for s in p:
                if s in dic:
                    cur_skill |= 1 << dic[s]
            for skill_set, team in list(dp.items()):
                new_skill = skill_set | cur_skill
                if new_skill != skill_set:
                    if new_skill not in dp or len(team) + 1 < len(dp[new_skill]):
                        dp[new_skill] = team + [i]
        return dp[(1 << n) - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_idx = {s: i for i, s in enumerate(req_skills)}
        n = len(req_skills)
        
        def encode(p):
            res = 0
            for sk in p:
                res |= 1 << skill_idx[sk]
            return res
        
        people_code = [encode(p) for p in people]
        target = (1 << n) - 1
        people_arr = 0
        m = len(people)
        
        
        covers = {0: []}
        for i, pcode in enumerate(people_code):
            for code, people_arr in list(covers.copy().items()):
                new_code = pcode | code
                if new_code in covers and len(people_arr) >= len(covers[new_code]):
                    continue
                covers[new_code] = people_arr + [i]
        return covers[target]
                    
            
        
                    
        
                
            


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        ##dp[i][state]: state: 0 ---- 2^n,  n = len(req_skills)
        ##dp[i][state] if state all included in people[i] --> dp[i-1][state]
        ##dp[i][state - subset] if subset in people[i] --> dp[i-1][state-subset] + 1
        \"\"\"
        m = len(req_skills)
        n = len(people)
        states = 1<<(m)
        skill_index = {}
        for i,skill in enumerate(req_skills):
            skill_index[skill] = i
        mypeople = []
        for p in people:
            myp = 0
            for skill in p:
                myp ^= (1 << skill_index[skill])
            mypeople.append(myp)
        
        dp = [float(\"inf\") for _ in range(states)]
        parent = [(-1, -1) for _ in range(states)]
        dp[0] = 0
        
        for i in range(n):
            skill = mypeople[i]
            if skill == 0:
                continue
            #for j in range(states)：
            #    if dp[i-1][j] != float(\"inf\"):
            #        dp[i][j] = dp[i-1][j]

            for j in range(states-1, -1, -1):
                if  dp[j] + 1 < dp[j|skill]:
                    dp[j | skill] = dp[j] + 1
                    parent[j | skill] = (j, i)
                    print(\"parent\", parent)
                if dp[i-1][j] + 1 < dp[i-1][j|skill] and dp[i-1][j] + 1 < dp[i][j|skill]:
                    parent[j|skill] = (j, i-1)
                dp[i][j|skill] = min(dp[i][j|skill], dp[i-1][j|skill], dp[i-1][j] + 1)
            print(i, dp)
                
        #print(\"dp\", dp)
        #print(\"parents\", parent)
        ans = []
        t = states - 1
        while t > 0:
            ans.append(parent[t][1])
            t = parent[t][0]
        print(\"ans\", ans)
        ans.reverse()
        return ans
        \"\"\"
        m, n = len(req_skills), len(people)
        key = {v:i for i,v in enumerate(req_skills)}
        #print(m, n, key)
        paths = {0: []} 
        for i, who in enumerate(people):
            his_skill = 0
            for skill in people[i]:
                if skill in key:
                    his_skill |= (1 << key[skill])
            
            for skills, path in list(paths.items()):
                new_skill = skills | his_skill
                if new_skill == skills: continue
                if new_skill not in paths or len(paths[new_skill]) > len(path) + 1:
                    paths[new_skill] = path + [i]
            #print(i, \"paths\", paths)
        return paths[(1 << m) - 1]
            
        
            
                

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic = {v: i for i, v in enumerate(req_skills)}
        dp = dict()
        for i, people_skill in enumerate(people):
            skill = 0
            for single_skill in people_skill:
                skill |= 1 << (dic[single_skill])
            dp[skill] = [i]
            for key, value in list(dp.items()):
                if key != skill:
                    new_skill = key | skill
                    if new_skill not in list(dp.keys()) or len(dp[new_skill]) > len(dp[key]) + 1:
                        dp[new_skill] = dp[key] + [i]
        
        return dp[(1 << len(req_skills)) - 1]
        
            
        


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_id_map = {skill: 1<<i for i, skill in enumerate(req_skills)}
        
        # key: bit representation of union of skills.
        # value: indices of people that comprise the smallest sufficient team.
        ids_indices_map = { 0: [] }

        for index, person_skills in enumerate(people):
            person_ids = 0
            for skill in person_skills:
                person_ids |= skill_id_map[skill]
            
            new_ids_indices_map = ids_indices_map.copy()
            for ids, indices in ids_indices_map.items():
                new_ids = ids | person_ids
                new_indices = indices + [index]
                if len(new_indices) <= len(new_ids_indices_map.get(new_ids, new_indices)):
                    new_ids_indices_map[new_ids] = new_indices
            
            ids_indices_map = new_ids_indices_map
        return ids_indices_map[2 ** len(req_skills) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:        
        n = len(req_skills)
        m = len(people)
        key = {v:i for i, v in enumerate(req_skills)}
        dp = {0 : []}
        
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                his_skill |= 1 << key[skill]
            
            
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
                    
        return dp[(1 << n) - 1]
    
    
    
    
        # n, m = len(req_skills), len(people)
        # key = {v: i for i, v in enumerate(req_skills)}
        # dp = {0: []}
        # for i, p in enumerate(people):
        #     his_skill = 0
        #     for skill in p:
        #         if skill in key:
        #             his_skill |= 1 << key[skill]
        #     if his_skill == 0:
        #         continue
        #     # if his_skill in dp and len(dp[his_skill]) == 1:
        #     #     continue
        #     for skill_set, need in list(dp.items()):
        #         with_him = skill_set | his_skill
        #         if with_him == skill_set: continue
        #         if with_him not in dp or len(dp[with_him]) > len(need) + 1:
        #             dp[with_him] = need + [i]
        # return dp[(1 << n) - 1]
                
            
            
     
        
        
        

        



from collections import Counter, defaultdict, OrderedDict, deque
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from typing import List
import itertools
import math
import heapq
import string
true = True
false = False
MIN, MAX, MOD = -0x3f3f3f3f, 0x3f3f3f3f, 1000000007


#
# @lc app=leetcode id=1125 lang=python3
#
# [1125] Smallest Sufficient Team
#
# https://leetcode.com/problems/smallest-sufficient-team/description/
#
# algorithms
# Hard (46.48%)
# Total Accepted:    8.6K
# Total Submissions: 18.5K
# Testcase Example:  '[\"java\",\"nodejs\",\"reactjs\"]\
[[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]'
#
# In a project, you have a list of required skills req_skills, and a list of
# people.  The i-th person people[i] contains a list of skills that person
# has.
#
# Consider a sufficient team: a set of people such that for every required
# skill in req_skills, there is at least one person in the team who has that
# skill.  We can represent these teams by the index of each person: for
# example, team = [0, 1, 3] represents the people with skills people[0],
# people[1], and people[3].
#
# Return any sufficient team of the smallest possible size, represented by the
# index of each person.
#
# You may return the answer in any order.  It is guaranteed an answer
# exists.
#
#
# Example 1:
# Input: req_skills = [\"java\",\"nodejs\",\"reactjs\"], people =
# [[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]
# Output: [0,2]
# Example 2:
# Input: req_skills = [\"algorithms\",\"math\",\"java\",\"reactjs\",\"csharp\",\"aws\"],
# people =
# [[\"algorithms\",\"math\",\"java\"],[\"algorithms\",\"math\",\"reactjs\"],[\"java\",\"csharp\",\"aws\"],[\"reactjs\",\"csharp\"],[\"csharp\",\"math\"],[\"aws\",\"java\"]]
# Output: [1,2]
#
#
# Constraints:
#
#
# 1 <= req_skills.length <= 16
# 1 <= people.length <= 60
# 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
# Elements of req_skills and people[i] are (respectively) distinct.
# req_skills[i][j], people[i][j][k] are lowercase English letters.
# Every skill in people[i] is a skill in req_skills.
# It is guaranteed a sufficient team exists.
#
#
#
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str],
                               people: List[List[str]]) -> List[int]:
        len_req, len_people = len(req_skills), len(people)
        skill2index = dict((s, i) for i, s in enumerate(req_skills))
        dp = {0: []}
        for i, p in enumerate(people):
            cur_skill = reduce(lambda a, b: a | (1 << skill2index[b]), p, 0)
            for skill_set in list(dp.keys()):
                need = dp[skill_set]
                hire_him = skill_set | cur_skill
                if hire_him not in dp or len(dp[hire_him]) > len(need) + 1:
                    dp[hire_him] = need + [i]
        return dp[(1 << len_req) - 1]


sol = Solution()

# req_skills = [\"java\",\"nodejs\",\"reactjs\"], people = [[\"java\"],[\"nodejs\"],[\"nodejs\",\"reactjs\"]]
req_skills, people = [
    \"algorithms\", \"math\", \"java\", \"reactjs\", \"csharp\", \"aws\"
], [[\"algorithms\", \"math\", \"java\"], [\"algorithms\", \"math\", \"reactjs\"],
    [\"java\", \"csharp\", \"aws\"], [\"reactjs\", \"csharp\"], [\"csharp\", \"math\"],
    [\"aws\", \"java\"]]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:        
        n = len(req_skills)
        m = len(people)
        key = {v:i for i, v in enumerate(req_skills)}
        dp = {0 : []}
        
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                his_skill |= 1 << key[skill]
            if his_skill == 0:
                continue
            
            
            for skill_set, need in list(dp.items()):
                with_him = skill_set | his_skill
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
                    
        return dp[(1 << n) - 1]
    
    
    
    
        # n, m = len(req_skills), len(people)
        # key = {v: i for i, v in enumerate(req_skills)}
        # dp = {0: []}
        # for i, p in enumerate(people):
        #     his_skill = 0
        #     for skill in p:
        #         if skill in key:
        #             his_skill |= 1 << key[skill]
        #     if his_skill == 0:
        #         continue
        #     # if his_skill in dp and len(dp[his_skill]) == 1:
        #     #     continue
        #     for skill_set, need in list(dp.items()):
        #         with_him = skill_set | his_skill
        #         if with_him == skill_set: continue
        #         if with_him not in dp or len(dp[with_him]) > len(need) + 1:
        #             dp[with_him] = need + [i]
        # return dp[(1 << n) - 1]
                
            
            
     
        
        
        

        



from functools import reduce

import operator

class Solution:
  def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
    # n: num skills
    n = len(req_skills)
    # z: target
    z = (1 << n) - 1
    # rs: hash of skill to integer 
    rs = {x: 1 << i for i, x in enumerate(req_skills)}
    # ps: hash people skill to integer
    ps = list(map(lambda p: reduce(operator.__or__, map(lambda s: rs[s], p), 0), people))
    # d: skillset to smallest sufficient team
    d = {0: []}
    # O(2^N M), N = num of skills, M = num of people
    for i, s in enumerate(ps):
      p = {}
      for x in d:
        y = x | s
        if y not in p or len(d[x]) < len(p[y]):
          p[y] = d[x] + [i]
      for y in p:
        if y not in d or len(p[y]) < len(d[y]):
          d[y] = p[y]
    return d[z]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        res = {}
        res[0] = set()
        skill_map = {v: i for i, v in enumerate(req_skills)}
        print(skill_map)
        
        for p, skills in enumerate(people):
            curr_skill = 0
            for skill in skills:
                curr_skill |= (1 << skill_map[skill])
            # print(curr_skill)
            
            nr = {}
            for s, t in res.items():
                k = curr_skill | s
                nt = t | {p}
                if k not in res:
                    if k not in nr or len(nr[k]) > len(nt): nr[k] = nt
                elif len(res[k]) > len(nt):
                    res[k] = nt
            res.update(nr)
            # print(res, nr)
        
        return list(res[(1 << n) - 1])

class Solution:            
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        l = len(req_skills)
        index_dict = {item : i for i, item in enumerate(req_skills)}
        mydict = {0 : []}
        for i, person in enumerate(people):
            skill_list = ['0']*l
            for skill in person:
                index = index_dict[skill]
                skill_list[index] = '1'
            num = int(''.join(skill_list), 2)
            new_dict = {key: list(item) for key, item in list(mydict.items())}
            for key in list(mydict.keys()):
                new_num = key | num
                if new_num in new_dict:
                    if len(new_dict[new_num]) > 1 + len(mydict[key]):
                        new_dict[new_num] = mydict[key] + [i,]
                else:
                    new_dict[new_num] = mydict[key] + [i,]
            mydict = new_dict
        return mydict[2**l-1]
                                    
            
                


class Solution:
    def smallestSufficientTeam(self, \\
                               req_skills: List[str], \\
                               people: List[List[str]]) -> List[int]:
        
        N = len(req_skills)
        P = len(people)
        
        skill_id_map = {skill:idx for idx,skill in enumerate(req_skills)}
        def get_ssid(skills):
            ssid = 0
            for skill in skills:
                idx = skill_id_map[skill]
                ssid |=  (1 << idx)
            return ssid
                
        people_ssid_map = {
            idx:get_ssid(skills) for idx,skills in enumerate(people)
        }
            
        dpv = [sys.maxsize] * (2**N)
        dpv[0] = 0
        dps = [[] for _ in range(2**N)]
        
        for ssid in range(2**N):
            if dpv[ssid] == sys.maxsize:
                continue
            for peepsid in range(P):
                skillset_id = people_ssid_map[peepsid]
                
                new_ssid = (ssid | skillset_id)
                if new_ssid != ssid:
                    if 1 + dpv[ssid] < dpv[new_ssid]:
                        dpv[new_ssid] = 1 + dpv[ssid]
                        dps[new_ssid] = dps[ssid] + [peepsid]
                    
        #print(dpv)
                    
        return dps[(2**N) - 1]
                    
                    
                
            
        

from collections import defaultdict

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def backtrack(i, people_added, skills_added):
            nonlocal result
            if i == len(req_skills):
                result = list(people_added)
            elif i in skills_added:
                backtrack(i+1, people_added, skills_added)
            else:
                if len(people_added) < len(result) - 1:
                    for k, skills_ix in list(skills_dict.items()):
                        if i in skills_ix:
                            backtrack(i+1, people_added + [k], skills_added | skills_ix)
                            
        result = list(range(len(req_skills)+1))
        req_skills_ix_map = {skill: i for i, skill in enumerate(req_skills)}
        skills_dict = {i: set([req_skills_ix_map[skill] for skill in skills]) for i, skills in enumerate(people)}
        backtrack(0, [], set())
        return result


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        target = (1<<n)-1
        s_i = {s:i for i,s in enumerate(req_skills)}
        # skill cost
        dp = {0:[]}
        for j,row in enumerate(people):
            mask = 0
            new_dp = dp.copy()
            for s in row:
                mask|= (1<<s_i[s])
            for curr,cost in dp.items():
                new_mask = curr|mask
                if new_mask not in new_dp:
                    new_dp[new_mask] = cost+[j]
                else:
                    new_dp[new_mask] = min(new_dp[new_mask],cost+[j],key=len)
            dp = new_dp
        return dp[target]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        L = len(req_skills)
        
        d = {}
        mask = 1
        for i in req_skills:
            d[i] = mask
            mask <<= 1
        
        p = [0] * len(people)
        for i, lst in enumerate(people):
            p[i] += sum([d[j] for j in lst])
    
        @functools.lru_cache(None)
        def dp(mask):
            if mask == 2 ** L - 1:
                return []

            smallest = float(\"inf\")
            ret = []
            for i, skills in enumerate(p):
                if mask & skills != skills:
                    tmp = dp(mask | skills)
                    if len(tmp) < smallest:
                        smallest = len(tmp)
                        ret = [i] + tmp
            return ret
        
        return dp(0)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        L = len(req_skills)
        
        d = {}
        mask = 1
        for i in req_skills:
            d[i] = mask
            mask <<= 1
        
        p = [0] * len(people)
        for i, lst in enumerate(people):
            p[i] += sum([d[j] for j in lst])
            
        print(p)
    
        @functools.lru_cache(None)
        def dp(mask):
            if mask == 2 ** L - 1:
                return []

            smallest = float(\"inf\")
            ret = []
            for i, skills in enumerate(p):
                if mask & skills != skills:
                    tmp = dp(mask | skills)
                    if len(tmp) < smallest:
                        smallest = len(tmp)
                        ret = [i] + tmp
            return ret
        
        return dp(0)

class Solution:
    def smallestSufficientTeam(self, skills: List[str], people: List[List[str]]) -> List[int]:
        skill2idx = {skill:i for i,skill in enumerate(skills)}
        for i in range(len(people)):
            mask = 0
            for skill in people[i]:
                mask |= (1 << skill2idx[skill])
            people[i] = mask
        stop = (1 << len(skills)) - 1
        
        @lru_cache(None)
        def dfs(i, mask):
            if mask == stop:
                return ()
            
            if i == len(people):
                return None
            
            ans1 = dfs(i+1, mask)
            ans2 = dfs(i+1, mask | people[i])
            if ans2 is not None:
                ans2 = (i,) + ans2
                
            if ans1 is None:
                return ans2
            elif ans2 is None:
                return ans1
            else:
                return min(ans1, ans2, key=len)
        
        return dfs(0, 0)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        pmasks = []
        for p in people:
            mask = 0
            for skill in p:
                idx = req_skills.index(skill)
                mask ^= 1 << idx
            pmasks.append(mask)
        M = pow(2, len(req_skills)) - 1
        
        @functools.lru_cache(maxsize=None)
        def dfs(mask):
            if mask == M:
                return []
            ret = None
            
            for i, p in enumerate(pmasks):
                if mask|p != mask:
                    ppl = dfs(mask|p)
                    if ppl != None and (not ret or len(ret) > len(ppl) + 1):
                        ret = [i] + ppl
                        #print(i, ppl)
            #print(mask, ret)
            return ret
        
        #print(M, pmasks)
        return dfs(0)

from functools import lru_cache
from collections import defaultdict
import math
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        mp = defaultdict(int)
        for i, skill in enumerate(req_skills):
            mp[skill] = i
        skills = []
        for p in people:
            mask = 0
            for skill in p:
                mask |= 1 << mp[skill]
            skills.append(mask)

        @lru_cache(None)
        def search(i: int, required: int) -> int:
            if required == 0:
                return 0
            if i == len(people):
                return math.inf
            return min(search(i + 1, required), 1 + search(i + 1, required ^ (required & skills[i])))
        
        def get_team(i: int, required: int, ans: list):
            if i == len(people):
                return
            if search(i + 1, required) > 1 + search(i + 1, required ^ (required & skills[i])):
                ans.append(i)
                get_team(i + 1, required ^ (required & skills[i]), ans)
            else:
                get_team(i + 1, required, ans)
        
        ans = []
        get_team(0, (1 << len(req_skills)) - 1, ans)
        return ans

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        N, M = len(req_skills), len(people)
        NN = 1 << N
        skill2id = {jj: ii for ii, jj in enumerate(req_skills)}
        team = {ii: [] for ii in range(NN)}
        dp = [-1] * NN
        dp[0] = 0

        for ii in range(M):
            idx = 0
            for s in people[ii]:
                if s in skill2id:
                    idx = idx | (1 << skill2id[s])
            for jj in range(NN):
                if dp[jj] < 0:
                    continue
                x = jj | idx
                if dp[x] == -1 or dp[x] > dp[jj] + 1:
                    # print(ii, jj, x, team)
                    dp[x] = dp[jj] + 1
                    team[x] = team[jj].copy()
                    team[x].append(ii)
        # print(team)
        return team[NN - 1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skill_id = {skill: i for i, skill in enumerate(req_skills)}
        def getSkillSetId(skills):
            res = 0
            for skill in skills:
                if skill in skill_id:
                    res |= (1 << skill_id[skill])
            return res
        
        req_skills = getSkillSetId(req_skills)
        people = list(map(getSkillSetId, people))
        
        @functools.lru_cache(None)
        def dfs(req_skills, pid):
            if req_skills == 0:
                return [0, []]
            elif pid == -1:
                return [float('inf'), []]
            else:
                sol1 = dfs(req_skills, pid - 1)
                sol2 = dfs(req_skills & (~people[pid]), pid - 1)
                if sol2[0] + 1 < sol1[0]:
                    return [sol2[0] + 1, sol2[1] + [pid]]
                else:
                    return sol1
        return dfs(req_skills, len(people) - 1)[1]
        
    
    def smallestSufficientTeam_II(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        
        skill_id = {skill:idx for idx, skill in enumerate(req_skills)}
        
        def getSkillId(skill_set):
            res = 0
            for skill in skill_set:
                res = res | ((1 << skill_id[skill]) if skill in skill_id else 0)
            return res
        
        people = [getSkillId(skills) for skills in people]
        req_skills = getSkillId(req_skills)
        
        @functools.lru_cache(maxsize = None)
        def dfs(req_skills, pid):
            if req_skills == 0:
                return [0, []]
            elif pid == len(people):
                return [float('inf'), []]
            else:
                sol1 = dfs(req_skills, pid + 1)
                sol2 = dfs(req_skills & ( ~people[pid]), pid + 1)
                if sol2[0] + 1 < sol1[0]:
                    return [sol2[0] + 1, [pid] + sol2[1]]
                else:
                    return sol1
        
        return dfs(req_skills, 0)[1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        # Similar to Knapsack problem. First use a binary string to represent a skill set, with target being 2^n-1 (if 3 skills are required, target will be 111). 
        # dp[i][j] := min people to reach skill set represented by binary string using first i people
        # dp[0][0] = 0
        # dp[i][j | k] = min(dp[i-1][j | k], dp[i-1][j] + 1), where k is the ith person's skillset.
        # if you have a skillset k of 100 and current j is 001, you can achieve a skillset new j of 100 | 001 = 101. So j of 101 can be achieved either with selecting me which is dp[i-1][j] + 1, or not selecting me - which is equivalent to achieving skillset of j | k with i-1 people, so dp[i-1][j|k]. Now we need to keep a pt (parent child relationship) to later link all the nodes we have traveled to get to the optimal answer dp[n][2^n-1].
        n = len(req_skills)
        target = (1<<n)-1
        skills = []
        for p in people:
            mask = 0
            for s in p:
                mask |= 1 << req_skills.index(s)
            skills.append(mask)
        dp = [float('inf') for _ in range(1 << n)]
        pt = [0 for _ in range(1 << n)]
        dp[0] = 0
        for i in range(len(people)):
            k = skills[i]
            if k == 0:
                continue
            for j in range(target+1)[::-1]:
                if dp[j] + 1 < dp[j|k]:
                    dp[j|k] = dp[j]+1
                    pt[j|k] = (j, i) # (parent, current)
        t = target
        ans = []
        while t:
            ans.append(pt[t][1])
            t = pt[t][0]
        return ans
                


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        allneed = (1 << len(req_skills) ) - 1

        stoi = {}
        for i, s in enumerate(req_skills):
            stoi[s] = 1 << i
        
        def serialize(arr):
            res = 0
            for s in arr:
                res = res | stoi[s]
            return res
        
        ppl = []
        for i,p in enumerate(people):
            ppl.append(serialize(p))
        
        tempmax = [0] * (len(req_skills) + 1)
        
        @lru_cache(None)
        def helper(needed):
            if needed == 0: return []
            shortest = tempmax
            for i, person in enumerate(ppl):
                if (person & needed) > 0:
                    sofar = [i] + helper((person ^ allneed) & needed)
                    if (len(sofar) < len(shortest)):
                        shortest = sofar
            return shortest
        
        return helper(allneed)


from functools import lru_cache

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        ids = {}
        sid = 0
        skills = 0
        for skill in req_skills:
            ids[skill] = sid
            skills = skills | (1 << sid)
            sid += 1

        n = len(people)

        @lru_cache(None)
        def dp(i, needed_skills):
            if needed_skills == 0:
                return []
            if i == n:
                return None

            a = dp(i + 1, needed_skills)

            next_needed_skills = needed_skills
            for s in people[i]:
                if s in ids:
                    j = ids[s]
                    next_needed_skills = (next_needed_skills & ~(1 << j))

            b = None
            if next_needed_skills != needed_skills:
                b = dp(i + 1, next_needed_skills)

            if a is not None and b is not None:
                if len(a) < len(b) + 1:
                    return a
                else:
                    return [i] + b

            if a is None and b is None:
                return None

            return ([i] + b) if a is None else a

        return dp(0, skills)





class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        skills = []
        for p in people:
            cur = 0
            for skill in p:
                for i, req_skill in enumerate(req_skills):
                    if skill == req_skill:
                        cur |= (1 << i)
            skills.append(cur)
        
        n = len(req_skills)
        target = (1 << n) - 1
        dp = [1000000 for i in range(target + 1)]
        dp[0] = 0
        # parent[k] = (j, i) means the skillset represented by k is constructed from skilset represented by j plus the skillset of ith people. from j to k we use i. In this way we can construct the result backward and 
        parent = [0] * (target + 1)
        
        for i in range(len(people)):
            k = skills[i]
            if k == 0:
                continue
            
            for j in reversed(list(range(target))):
                if dp[j | k] > dp[j] + 1:
                    dp[j | k] = dp[j] + 1
                    parent[j | k] = (j, i)
        
        t = target
        result = []
        while t:
            result.append(parent[t][1])
            t = parent[t][0]
        return result
        


from functools import lru_cache

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        ids = {}
        sid = 0
        skills = 0
        for skill in req_skills:
            ids[skill] = sid
            skills = skills | (1 << sid)
            # print(sid, 1 << sid)
            sid += 1

        # print(ids)
        # print(skills)

        n = len(people)

        @lru_cache(None)
        def dp(i, left):
            if left == 0:
                return []
            if i == n:
                return None

            a = dp(i + 1, left)

            for s in people[i]:
                if s in ids:
                    j = ids[s]
                    left = (left & ~(1 << j))

            b = dp(i + 1, left)

            if a is not None and b is not None:
                if len(a) < len(b) + 1:
                    return a
                else:
                    return [i] + b

            if a is None and b is None:
                return None

            return ([i] + b) if a is None else a

        return dp(0, skills)


from functools import lru_cache

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        all_skills = (1 << n) - 1
        max_team = [0] * len(people)

        def construct_mask(skills):
            mask = 0
            for skill in skills:
                mask |= 1 << req_skills.index(skill)
            return mask

        people = [construct_mask(skills) for skills in people]

        @lru_cache(maxsize=None)
        def min_team(idx, skills):
            if skills == all_skills:
                return []

            if idx >= len(people):
                return None

            team = max_team
            for i in range(idx, len(people)):
                temp_mask = skills | people[i]
                if temp_mask == skills:
                    continue

                other_people = min_team(i + 1, temp_mask)
                if other_people is None:
                    continue

                if len(other_people) + 1 < len(team):
                    team = [i] + other_people

            return team

        return min_team(0, 0)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        #return what people to use 
        #dp[i][j] : min people to has skill set of j using first i people
        #dp[0][0] = 0
        # n skillset, total combine: 2^n -1
        n = len(req_skills)
        target = ( 1<<n ) - 1
        dic = {x: index for index, x in enumerate(req_skills)} 
        skillsMap = []
        for i in people:
            mask = 0
            for sk in i:
                mask |=(1<< dic[sk])
            skillsMap.append(mask)
        dp = [float('inf')]  * (1<<n)
        par = [(0,0)] *(1<<n)
        dp[0] = 0
        for i, k in enumerate(skillsMap):
            if k != 0:
                for j in range(target, -1, -1):
                    if dp[j] + 1 < dp[j | k]:
                        dp[j|k] = dp[j] + 1
                        par[j|k] = (j, i)
                        
        res = []
        while target:
            res.append(par[target][1])
            target = par[target][0]
        return res


class Solution:
    from collections import defaultdict
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic={req_skills[rs]:2**rs for rs in range(len(req_skills))}
        dp={i:[] for i in range(2**len(req_skills))}
        m_pp=[]
        for pp in range(len(people)):
            # temp=dp.copy()
            res=0
            for itr_pp in people[pp]:
                res+=dic[itr_pp]
            # print(res, people[pp])
            if res!=0:
                dp[res]=[pp]
                for j in list(dp.keys()):
                    if len(dp[j])>0:
                        sum_=j|res
                        if len(dp[sum_])==0 or len(dp[sum_])>len(dp[j]+[pp]):
                                dp[sum_]=dp[j]+[pp]
                # dp=temp
        # def recur(idx,val,res):
        #     if len(dp[val])==0 or len(dp[val])>len(res):
        #         dp[val]=res
        #     if len(dp[val])<len(res):return
        #     if idx==len(m_pp):return
        #     for i in range(idx,len(m_pp)):
        #         # print(res,[i])
        #         if m_pp[i]==0:continue
        #         recur(i+1,val|m_pp[i],res+[i])
        # recur(0,0,[])
        # print(dp)
        return dp[2**len(req_skills)-1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        INT_MAX = 2147483647
        n = len(req_skills)
        pskills = list()
        target = (1 << n) - 1
        dp = [INT_MAX for i in range(target+1)]
        parent = [list() for i in range(target+1)]
        umap = dict()
        
        for i in range(n):
            umap[req_skills[i]] = i
        
        for p in people:
            mask = 0
            for sk in p:
                mask |= (1<<umap[sk])
            pskills.append(mask)
            
        dp[0] = 0
        pLen = len(people)
        for i in range(pLen):
            k = pskills[i]
            if k == 0:
                continue
            for j in range(target+1):
                if (dp[j|k] > dp[j]+1):
                    dp[j|k] = dp[j] + 1
                    parent[j|k] = [j, i]
        
        t = target
        result = list()
        while t > 0:
            result.append(parent[t][1])
            t = parent[t][0]
        return result

from collections import defaultdict

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        def backtrack(i, people_added, skills_added):
            nonlocal result
            if i == len(req_skills):
                result = list(people_added)
            elif req_skills[i] in skills_added:
                backtrack(i+1, people_added, skills_added)
            else:
                if len(people_added) < len(result) - 1:
                    for k, skills in list(skills_dict.items()):
                        if req_skills[i] in skills:
                            backtrack(i+1, people_added + [k], skills_added | skills)
                            
        result = list(range(len(req_skills)+1))
        skills_dict = {i: set(skills) for i, skills in enumerate(people)}
        backtrack(0, [], set())
        return result


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v: i for i, v in enumerate(req_skills)}
        dp = [[]] + [None] * ((1 << n) - 1)
        for i, p in enumerate(people):
            his_skill = 0
            for skill in p:
                if skill in key:
                    his_skill |= 1 << key[skill]
            for k in range(len(dp)-1, -1, -1):
                with_him = k | his_skill
                if with_him == k or dp[k] is None: continue
                if not dp[with_him] or len(dp[k]) + 1 < len(dp[with_him]):
                    dp[with_him] = dp[k] + [i]
        return dp[(1 << n) - 1]

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic={req_skills[rs]:2**rs for rs in range(len(req_skills))}
        dp=[[] for i in range(2**len(req_skills))]
        m_pp=[]
        for pp in range(len(people)):
            res=0
            for itr_pp in people[pp]:
                res+=dic[itr_pp]
            # print(res, people[pp])
            if res!=0:
                dp[res]=[pp]
            m_pp.append(res)
        # def recur(idx,val,res):
        #     if len(dp[val])==0 or len(dp[val])>len(res):
        #         dp[val]=res
        #     if len(dp[val])<len(res):return
        #     if idx==len(m_pp):return
        #     for i in range(idx,len(m_pp)):
        #         # print(res,[i])
        #         if m_pp[i]==0:continue
        #         recur(i+1,val|m_pp[i],res+[i])
        for i in range(len(m_pp)):
            if m_pp[i]==0:continue
            for j in range(len(dp)):
                if len(dp[j])>0:
                    sum_=j|m_pp[i]
                    if len(dp[sum_])==0 or len(dp[sum_])>len(dp[j]+[i]):
                            dp[sum_]=dp[j]+[i]
        # recur(0,0,[])
        return dp[-1]


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        l = len(req_skills)
        skill_to_idx = {s:i for i, s in enumerate(req_skills)}
        
        
        @functools.lru_cache(None)
        def dfs(cur_skill, idx):
            if cur_skill == 2**l-1:
                return ()
            if idx == len(people):
                return None
            
            cur = 0
            for skill in people[idx]:
                if skill in skill_to_idx and 1 << skill_to_idx[skill] & cur_skill == 0:
                    cur |= 1 << skill_to_idx[skill]
            ret = dfs(cur_skill, idx+1)
            if cur != 0:
                tmp = dfs(cur_skill | cur, idx+1)
                if tmp != None and ret != None:
                    ret = min(ret, tuple([idx, *tmp]), key=len)
                elif tmp != None:
                    ret = tuple([idx, *tmp])
            return ret
        ret = dfs(0, 0)
        return ret


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        dic={req_skills[rs]:2**rs for rs in range(len(req_skills))}
        dp=[[] for i in range(2**len(req_skills))]
        m_pp=[]
        for pp in range(len(people)):
            res=0
            for itr_pp in people[pp]:
                res+=dic[itr_pp]
            # print(res, people[pp])
            if res!=0:
                dp[res]=[pp]
            m_pp.append(res)
        # def recur(idx,val,res):
        #     if len(dp[val])==0 or len(dp[val])>len(res):
        #         dp[val]=res
        #     if len(dp[val])<len(res):return
        #     if idx==len(m_pp):return
        #     for i in range(idx,len(m_pp)):
        #         # print(res,[i])
        #         if m_pp[i]==0:continue
        #         recur(i+1,val|m_pp[i],res+[i])
        for i in range(len(m_pp)):
            if m_pp[i]==0:continue
            # print('-------')
            dp[m_pp[i]]=[i]
            for j in range(len(dp)):
                if len(dp[j])>0:
                    sum_=j|m_pp[i]
                    # # if sum_==0:continue
                    # if j==len(dp)-1:
                    #     print(j,m_pp[i],j^sum_)
                    if len(dp[sum_])==0 or len(dp[sum_])>len(dp[j]+[i]):
                            dp[sum_]=dp[j]+[i]
                
#                 # tgt=dp[res|i]
#                 dp[m_pp[j]|m_pp[i]]=list(set(dp[m_pp[j]]+dp[m_pp[i]]))
#                 # if len(tgt)==0 or len(tgt)>len(new):dp[res|i]=new
        # recur(0,0,[])
        # for i in range(len(dp)):
        #     print(i,dp[i])
        # print(dp[-1])
        return dp[-1]


#[] DP
#O(N * 2^R) N: number of people, R: number of skills
#f(i, S): the minimum people count to use first i people to fulfill state S
#state S is a binary set which is a combinations of skills
#f(N, all 1) = 0,  f(N, not all 1) = inf
#return f(-1, 0)
#f(i, S) = min( f(i+1, S) , 1+f(i+1, S + req_skill[i])
def memorized(f):
    memo = {}
    def helper(*arg):
        if arg not in memo:
            memo[arg] = f(*arg)
        return memo[arg]
    return helper
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        N, MASK = len(people), (1 << len(req_skills))-1
        skill2id, child = {skill: i for i, skill in enumerate(req_skills)}, {}
        people = [sum(1 << skill2id[skill] for skill in skills) for skills in people]
        @memorized
        def dp(i: int, status: int) -> int:
            \"\"\"return the path to get into (i, status) node\"\"\"
            if i >= N:
                return [] if status == MASK else None
            not_choose, choose = dp(i+1, status), dp(i+1, status | people[i])
            if not_choose is not None and (choose is None or len(not_choose) <= len(choose) + 1):
                return not_choose
            else: #NOTE: handle the case that choose is None, too
                return choose + [i] if choose is not None else None
        return dp(-1, 0)

from functools import lru_cache
from collections import defaultdict
import math
class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        mp = defaultdict(int)
        for i, skill in enumerate(req_skills):
            mp[skill] = i
        skills = []
        for p in people:
            mask = 0
            for skill in p:
                mask |= 1 << mp[skill]
            skills.append(mask)

        @lru_cache(None)
        def search(i: int, required: int) -> int:
            if required == 0:
                return 0
            if i == len(people):
                return math.inf
            return min(search(i + 1, required), 1 + search(i + 1, required ^ (required & skills[i])))
        
        ans = []
        required = (1 << len(req_skills)) - 1
        for i in range(len(people)):
            if search(i + 1, required) > 1 + search(i + 1, required ^ (required & skills[i])):
                ans.append(i)
                required ^= required & skills[i]
        return ans

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        target = (1<<n)-1
        skills = []
        for p in people:
            mask = 0
            for s in p:
                mask |= 1 << req_skills.index(s)
            skills.append(mask)
        dp = [float('inf')/2 for _ in range(1 << n)]
        pt = [0 for _ in range(1 << n)]
        dp[0] = 0
        for i in range(len(people)):
            k = skills[i]
            if k == 0:
                continue
            for j in range(target+1)[::-1]:
                if dp[j] + 1 < dp[j|k]:
                    dp[j|k] = dp[j]+1
                    pt[j|k] = (j, i) # (parent, current)
        t = target
        ans = []
        while t:
            ans.append(pt[t][1])
            t = pt[t][0]
        return ans
                


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        s2i = {}
        for i, skill in enumerate(req_skills):
            s2i[skill] = i
        
        n = len(people)
        p2n = [0] * n
        for i, p in enumerate(people):
            temp = 0
            for skill in p:
                temp |= 1 << s2i[skill]
            p2n[i] = temp
        
        goal = (1 << len(req_skills)) - 1
        dp = [sys.maxsize] * (goal + 1)
        dp[0] = 0
        saves = [[] for i in range(goal + 1)]

        for i in range(n):
            skill = p2n[i]
            for skillset in range(goal + 1):
                new_skill = skillset | skill
                if dp[new_skill] > dp[skillset] + 1:
                    dp[new_skill] = dp[skillset] + 1
                    saves[new_skill] = list(saves[skillset])
                    saves[new_skill].append(i)
                    
        return saves[goal]


from collections import defaultdict
from functools import lru_cache

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        req_skills = set(req_skills)
        d = {}
        for i, x in enumerate(req_skills):
            d[x] = i
        
        @lru_cache(None)
        def dfs(state, idx):
            if state == 2 ** len(req_skills) - 1:
                return []
            if idx == len(people):
                return [0] * 100
            out = dfs(state, idx + 1)
            new_state = state
            for skill in people[idx]:
                new_state |= 1 << d[skill]
            new = dfs(new_state, idx + 1)
            if len(out) < len(new) + 1:
                return out
            return [idx] + new
        
        return dfs(0, 0)