liars

时间限制:10s      空间限制:128MB

题目描述

n个人,编号分别为1,2,?n。这n个人中每个人不是诚实者就是说谎者,并且每个人都知
道下一个人的身份(即第k个人知道第k+1个人的身份,1<=k<n,且第n个人知道第1个人的
身份)。现在已知每个人对他下一个人的身份的判断,并且说谎者的人数不超过t,问哪些
人一定是说谎者。注意,诚实者给出的判断一定是正确的,但说谎者给出的判断是不确定的,可能正确也可能错误。
 
 


输入格式

 
 
第一行一个整数T,表示数据个数。
下面接T组数据,每组数据两行。
第一行为两个正整数nt,表示一共有n个人,且说谎者人数不超过t
第二行为n个整数,每个数为01。第i个数若为0,则表示第i个人判断下一个人为诚实者;
若为1,则表示第i个人判断下一个人为说谎者。
 
 


输出格式

 
每组数据输出一行,每行两个整数。第一个整数表示一定是说谎者的人的个数,第二个数
表示一定是说谎者的人中,编号最小的人的编号。若第一个数是0,则第二个数也为0。(
若定义集合S={k|k个人一定是说谎者},那么第一个数就是|S|,第二个数就是S中最小的
数。若S为空集则第二个数为0
 
 
 
 


样例输入

3
5  2
0  1 1 0 0
7  2
0  0 1 0 0 1 1
9  8
1  0 0 0 0 1 0 0 0
 
 
 

样例输出

1  3
2  4
0  0
 
 
 

提示

n<=100000。


题目来源

贪心

Menuappsclose