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.

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Bit manipulation

Data structures

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
		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
		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 = [(deque(rare_skills), [])]
			while stack:
				(skills, team) = stack.pop()
				if not skills:
					return team
				if len(team) + 1 > i:
					continue
				skill = skills[0]
				for person in has_skill[skill]:
					remaining_skills = fulfill_skills(skills, person)
					stack.append((remaining_skills, team + [person]))
		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):
		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)
			temp = self.dfs(nextState, memo, peopleSkills, res, n, people, skillsMap)
			currState = list(bin(state)[3:])
			if len(temp) < mini:
				mini = len(temp)
				ans = [p] + temp
		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


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]:
		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]:
		(N, skill_dict) = (len(req_skills), {})
		for i in range(N):
			skill_dict[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 << skill_dict[s]
			for (k, v) in enumerate(dp):
				new_skill = k | skill
				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]:
		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]:
		(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()


import functools

class Solution:

	def smallestSufficientTeam(self, req_skills, people):
		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)
			newteamskills = teamskills | peopleskills[i]
			(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]


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)
		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)
		self.tar = 2 ** len(req_skills) - 1
		self.r_len = len(people)
		self.r = []

		def dfs(l, t, cur):
			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


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)


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]


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]:
		(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 []


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)
			elif 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]:

		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
		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
		rare_skills = [(len(people), skill) for (skill, people) in list(has_skill.items())]
		rare_skills.sort()
		rare_skills = [skill for (_, skill) in rare_skills]
		q = deque()
		q.append((deque(rare_skills), []))
		while q:
			(skills, team) = q.popleft()
			print((skills, team))
			if not skills:
				return team
			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]:
		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
			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]:
		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, 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]:
		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]


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 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]:
		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]


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)):
			res = 0
			for itr_pp in people[pp]:
				res += dic[itr_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]
		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]:
		skillid = {skill: i for (i, skill) in enumerate(req_skills)}
		skillsets = {0: []}
		for (i, p) in enumerate(people):
			skillmask = 0
			for skill in p:
				if skill in skillid:
					skillmask |= 1 << skillid[skill]
			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:

	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]:
		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)}
		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]


from functools import reduce
import operator

class Solution:

	def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
		n = len(req_skills)
		z = (1 << n) - 1
		rs = {x: 1 << i for (i, x) in enumerate(req_skills)}
		ps = list(map(lambda p: reduce(operator.__or__, map(lambda s: rs[s], p), 0), people))
		d = {0: []}
		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]
			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)
		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]


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)
			elif 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)}
		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, 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
			return ret
		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:
					dp[x] = dp[jj] + 1
					team[x] = team[jj].copy()
					team[x].append(ii)
		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]:
		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)
		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 = [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]:
		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]:
		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:

	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


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]
			if res != 0:
				dp[res] = [pp]
			m_pp.append(res)
		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]
		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]:
		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]