#2048. 序列划分

序列划分

说明

梦想从几时开始,命运在何处终结?

有一个长度为 nn 的整数序列 {a1,a2,,an}\{a_1, a_2, \cdots, a_n\}

你的任务是判断是否可以将其划分为 kk 的倍数个非空子序列,使得每个元素在恰一个子序列中出现,同时每个子序列均kk 的倍数开头、kk 的倍数结尾,并且长度也为 kk 的倍数。若能划分,求出任意一个方案。

序列 {a1,a2,,an}\{a_1, a_2, \cdots, a_n\} 的一个子序列是指将任意多个(可以为 00 个)元素删除后,将其他元素按照原序列中的顺序拼接而成的序列。例如,序列 {9,8,5}\{9, 8, 5\}、序列 {7}\{7\} 和序列 {9,8,7,6,5}\{9, 8, 7, 6, 5\} 均为序列 {9,8,7,6,5}\{9, 8, 7, 6, 5\} 的子序列,但 {7,9,8}\{7, 9, 8\} 不是。

输入格式

输入的第一行包含一个整数 TT —— 表示子任务编号(与「数据范围与提示」中编号相同,样例的子任务编号为 00)。

第二行包含两个空格分隔的正整数 n,kn,k —— 序列 aa 的长度和 kk 的值。

第三行包含 nn 个空格分隔的正整数 a1,a2,,ana_1, a_2, \cdots, a_n —— 依次表示序列 aa 的元素。

输出格式

若有解,则第一行输出 Yes,否则第一行输出 No。

若有解则按以下格式输出任意一个划分方案:

第二行输出一个整数 cc 表示划分成了 cc 个子序列,满足 kcnk\le c\le ncckk 的倍数;

接下来 cc 行每行描述一个子序列:

ii 行第一个整数 lil_i 表示第 ii 个子序列的长度,满足 klink\le l_i\le nlil_ikk 的倍数。

接下来 lil_i 个整数 pi,1,pi,2,,pi,lip_{i,1},p_{i,2},\cdots,p_{i,l_i} 表示这个子序列中元素的下标。满足 pi,j<pi,j+1p_{i,j}<p_{i,j+1}(即下标单调递增)且 api,1a_{p_{i,1}}api,lia_{p_{i,l_i}}kk 的倍数。

另外,1n1\sim n 中每个数在 pp 中出现且仅出现一次。

样例

0
6 2
2 4 1 3 6 8
Yes
2
2 1 5
4 2 3 4 6

划分为 {2,6}\{2, 6\}{4,1,3,8}\{4, 1, 3, 8\} 两个子序列满足条件。

0
6 2
2 4 6 1 3 5
No

kk 的倍数结尾什么的最讨厌了 (– ‸– )

0
6 2
2 1 2 2 1 2
Yes
2
4 1 2 5 6
2 3 4
0
15 3
3 1 1 1 1 3 3 1 3 3 1 1 1 1 3
Yes
3
6 1 2 3 4 5 10
6 6 11 12 13 14 15
3 7 8 9

数据范围

对于所有数据,有 2k,n106,0ai1062 \leq k,n \leq 10^6,0\le a_i\le 10^6

Subtask # 分值 nn 的限制 kk 的限制 特殊限制
1 55 n10n \le 10 k=2k = 2 -
2 1010 n20n \le 20 k20k \le 20
3 n5×104n \le 5\times 10^4 k=2k = 2
4 1515 n102n \le 10^2 k3k \le 3
5 1010 n103n \le 10^3 k103k \le 10^3
6 n5×104n \le 5\times 10^4 k5×104k \le 5\times 10^4 a1,a2,,aka_1,a_2,\cdots ,a_kkk 的倍数
7 存在方案使得 a1a_1ana_n 属于同一子序列
8 1515 -
9 n106n \le 10^6 k106k \le 10^6