← 返回题目列表

Codeforces · 1196/B

B. 奇数和段

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,由 $$$n$$$ 整数 $$$a_1、a_2、\dots、a_n$$$ 组成。您希望将其精确地拆分为 $$$k$$$ 非空非相交子段,使得每个子段的总和为奇数(即对于每个子段,属于该子段的所有元素的总和为奇数)。重新排列(打乱)给定数组的元素是不可能的。数组 $$$a$$$ 的每个 $$$n$$$ 元素必须恰好属于 $$$k$$$ 子段之一。

让我们看一些将长度 $$$5$$$ 的数组划分为 $$$3$$$ 子段(不一定是奇数)的示例: $$$[1, 2, 3, 4, 5]$$$ 是初始数组,然后将其划分为 $$$3$$$ 非空非相交子段的所有可能方法如下:

- $$$[1], [2], [3, 4, 5]$$$;
- $$$[1], [2, 3], [4, 5]$$$;
- $$$[1], [2, 3, 4], [5]$$$;
- $$$[1, 2], [3], [4, 5]$$$;
- $$$[1, 2], [3, 4], [5]$$$;
- $$$[1, 2, 3], [4], [5]$$$.

当然,不可能将初始数组精确地划分为 $$$k$$$ 个子段,并且每个子段的元素和均为奇数。在这种情况下打印“NO”。否则,打印“YES”以及数组的任何可能的划分。详细说明请参见输出格式。

您必须回答 $$$q$$$ 独立查询。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。然后是 $$$q$$$ 查询。

查询的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — 分别表示数组中元素的数量和子段的数量。

查询的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

保证所有查询的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个查询,打印其答案。如果不可能将初始数组精确地划分为 $$$k$$$ 子段,并且每个子段的元素和为奇数,则在第一行打印“NO”。否则,在第一行中打印“YES”,并在第二行中打印数组的任何可能的划分。除法可以表示为 $$$k$$$ 整数 $$$r_1$$$, $$$r_2$$$, ..., $$$r_k$$$,使得 $$$1 \le r_1 < r_2 < \dots < r_k = n$$$,其中 $$$r_j$$$ 是第 $$$j$$$ 段的右边界(属于该段的最后一个元素的索引) $$$j$$$-th 段),因此数组被分为子段 $$$[1; r_1],[r_1 + 1; r_2]、[r_2 + 1、r_3]、\点、[r_{k - 1} + 1、n]$$$。请注意,$$$r_k$$$ 始终是$$$n$$$,但无论如何你都应该打印它。

示例

输入 #1

3
5 3
7 18 3 14 1
5 4
1 2 3 4 5
6 2
1 2 8 4 10 2

输出 #1

YES
1 3 5
NO
NO