题目内容

在云服务中，有 $n$ 个安全策略，编号 $1$ 到 $n$。每个策略有一个重要度权重（正整数）。某些策略对之间互斥，不能同时启用。

现在需要为某个实例恰好选择 $k$ 个策略，要求：

1. 选中的策略之间没有互斥关系（即构成一个独立集）；
2. 在满足条件1的所有大小为 $k$ 的策略组合中，使得选中策略的权重之和最大（权重之和就是重要度权重数组中的权重的和）。

请返回所有满足上述条件的最优策略组合（即权重和最大的所有合法组合）。

输入描述

• 第一行：整数 $n$（策略总数）
• 第二行：整数 $k$（需要选择的策略数量）
• 第三行：长度为 $n$ 的整数数组 $weights$，其中 $weights[i]$ 表示策略 $i+1$ 的权重
• 第四行：二维整数数组 $conflicts$，每个元素为 [$a$, $b$]，表示策略 $a$ 和 $b$ 互斥（无向，无重复边）

输出描述

• 每个组合内的策略编号按升序排列；
• 所有组合按字典序排列（将每个组合视为一个数字序列）；
• 如果没有合法组合（例如不存在大小为 $k$ 的独立集），则返回空数组 []。

注意

• 如果没有大小为 $k$ 的独立集，则返回 []

数据规模

• $1 \le n \le 25$
• $0 \le k \le n$
• $1 \le$ $weights$[$i$] $\le 1000$
• $0 \le$ $conflicts.length$ $\le n(n-1)/2$

样例1

输入

4,2,[5,1,3,4],[[1,2],[2,3]]

输出

[[1,4]]

说明

所有大小为 $2$ 的策略组合及互斥检查：

其中权重和最大为 $9$，对应组合 $[1,4]$，故输出 $[[1,4]]$。

样例2

输入

5,3,[3,4,3,4,3],[[1,3],[2,4],[3,5]]

输出

[[1,2,5],[1,4,5]]

说明

所有大小为3且无互斥的组合：

合法组合只有 $[1,2,5]$ 和 $[1,4,5]$，权重和均为 $10$，是最大值。

按字典序排序：$[1,2,5] < [1,4,5]$，故输出 $[[1,2,5],[1,4,5]]$。