def bitmask_dp(n, items):
    # State: dp[mask] = value for subset represented by mask
    # Iterate over all 2^n subsets
    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):  # If i is in current subset
                prev_mask = mask ^ (1 << i)  # Subset without i
                dp[mask] = transition(dp[prev_mask], items[i])

    return dp[(1 << n) - 1]  # Full set

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

# dp[mask][last] = min cost to visit nodes in mask, ending at last
for mask in range(1, 1 << n):
    for last in range(n):
        if not (mask & (1 << last)):
            continue
        prev_mask = mask ^ (1 << last)
        for prev in range(n):
            if prev_mask & (1 << prev):
                dp[mask][last] = min(dp[mask][last],
                                     dp[prev_mask][prev] + cost[prev][last])

# dp[mask] = min items to cover skills in mask
for i in range(num_people):
    skill_mask = encode_skills(people[i])
    for mask in range(1 << num_skills):
        new_mask = mask | skill_mask
        dp[new_mask] = min(dp[new_mask], dp[mask] + 1)

def subsets(nums):
    n = len(nums)
    result = []

    # Enumerate all 2^n bitmasks
    for mask in range(1 << n):
        # Build subset from mask
        subset = []
        for i in range(n):
            if mask & (1 << i):  # Check if bit i is set
                subset.append(nums[i])
        result.append(subset)

    return result

from collections import deque

def shortestPathLength(graph):
    n = len(graph)
    if n == 1:
        return 0

    full_mask = (1 << n) - 1

    # State: (node, visited_mask)
    # Initialize: start from every node
    queue = deque()
    visited = set()

    for i in range(n):
        state = (i, 1 << i)
        queue.append((i, 1 << i, 0))  # (node, mask, distance)
        visited.add(state)

    while queue:
        node, mask, dist = queue.popleft()

        for neighbor in graph[node]:
            new_mask = mask | (1 << neighbor)

            if new_mask == full_mask:
                return dist + 1

            state = (neighbor, new_mask)
            if state not in visited:
                visited.add(state)
                queue.append((neighbor, new_mask, dist + 1))

    return -1  # Should never reach here for connected graph

def smallestSufficientTeam(req_skills, people):
    n = len(req_skills)
    skill_to_idx = {s: i for i, s in enumerate(req_skills)}

    # Encode each person's skills as bitmask
    person_masks = []
    for skills in people:
        mask = 0
        for skill in skills:
            if skill in skill_to_idx:
                mask |= (1 << skill_to_idx[skill])
        person_masks.append(mask)

    full_mask = (1 << n) - 1

    # dp[mask] = smallest team to achieve skill mask
    dp = {0: []}

    for i, person_mask in enumerate(person_masks):
        # Iterate over copy of current states
        for mask, team in list(dp.items()):
            new_mask = mask | person_mask

            # Only update if this gives a smaller team
            if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
                dp[new_mask] = team + [i]

    return dp[full_mask]

# Remove people whose skills are subset of another person
def prune_dominated(person_masks):
    n = len(person_masks)
    keep = [True] * n
    for i in range(n):
        for j in range(n):
            if i != j and (person_masks[i] | person_masks[j]) == person_masks[j]:
                # Person i is dominated by person j
                keep[i] = False
                break
    return [i for i in range(n) if keep[i]]

# All three problems use these operations:

# 1. Set bit i (add element)
mask | (1 << i)

# 2. Check bit i (is element present?)
mask & (1 << i)  # or (mask >> i) & 1

# 3. Full mask (all elements)
(1 << n) - 1

# 4. Iterate bits
for i in range(n):
    if mask & (1 << i):
        # Process element i

def enumerate_subsets(nums):
    """Generate all 2^n subsets using bitmask."""
    n = len(nums)
    result = []

    for mask in range(1 << n):
        # Decode bitmask to subset
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)

    return result

from collections import deque

def bfs_bitmask(graph):
    """BFS with (node, visited_mask) state."""
    n = len(graph)
    full_mask = (1 << n) - 1

    # Initialize: start from every node
    queue = deque()
    visited = set()

    for i in range(n):
        state = (i, 1 << i)
        queue.append((i, 1 << i, 0))  # (node, mask, dist)
        visited.add(state)

    while queue:
        node, mask, dist = queue.popleft()

        for neighbor in graph[node]:
            new_mask = mask | (1 << neighbor)

            # Early termination
            if new_mask == full_mask:
                return dist + 1

            state = (neighbor, new_mask)
            if state not in visited:
                visited.add(state)
                queue.append((neighbor, new_mask, dist + 1))

    return -1

def set_cover_dp(required_mask, item_masks):
    """
    Find minimum items to cover all requirements.

    Args:
        required_mask: Target mask to achieve
        item_masks: List of (item_id, mask) tuples

    Returns:
        List of item indices forming minimum cover
    """
    # dp[mask] = smallest set of items to achieve mask
    dp = {0: []}

    for item_id, item_mask in item_masks:
        # Iterate over copy of current states
        for mask, items in list(dp.items()):
            new_mask = mask | item_mask

            # Only update if strictly better
            if new_mask not in dp or len(dp[new_mask]) > len(items) + 1:
                dp[new_mask] = items + [item_id]

    return dp.get(required_mask, [])

def tsp_dp(dist):
    """
    Classic TSP: minimum cost to visit all nodes.

    Args:
        dist: n×n distance matrix

    Returns:
        Minimum cost to visit all nodes starting from node 0
    """
    n = len(dist)
    INF = float('inf')

    # dp[mask][last] = min cost to visit nodes in mask, ending at last
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start at node 0

    for mask in range(1, 1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            if dp[mask][last] == INF:
                continue

            for next_node in range(n):
                if mask & (1 << next_node):
                    continue

                new_mask = mask | (1 << next_node)
                dp[new_mask][next_node] = min(
                    dp[new_mask][next_node],
                    dp[mask][last] + dist[last][next_node]
                )

    full_mask = (1 << n) - 1
    return min(dp[full_mask])

# Essential bit operations

def set_bit(mask, i):
    """Add element i to set."""
    return mask | (1 << i)

def clear_bit(mask, i):
    """Remove element i from set."""
    return mask & ~(1 << i)

def has_bit(mask, i):
    """Check if element i is in set."""
    return (mask >> i) & 1

def toggle_bit(mask, i):
    """Toggle element i membership."""
    return mask ^ (1 << i)

def count_bits(mask):
    """Count elements in set."""
    return bin(mask).count('1')

def full_mask(n):
    """Create mask with all n bits set."""
    return (1 << n) - 1

def iterate_bits(mask, n):
    """Yield indices of set bits."""
    for i in range(n):
        if mask & (1 << i):
            yield i

def submasks(mask):
    """Iterate all submasks of mask (excluding 0)."""
    sub = mask
    while sub:
        yield sub
        sub = (sub - 1) & mask