P2447 [SDOI2010] 外星千足虫

公元 $2333$ 年 $2$ 月 $3$ 日，在经历了 $17$ 年零 $3$ 个月的漫长旅行后，“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局（NASA）研制发射，行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等 $23$ 颗太阳系星球，并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下 $45.70$ 米位置发现一批珍贵的活体生命样本，并将其带回检测。 在带回的活体样本中，最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长，身体分为若干节。受到触碰时，会将身体卷曲成圆环形，间隔一段时间后才会复原活动。 有趣的还不止如此。研究人员发现，这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足，但足的总数一定是奇数条！ 虽然从外观难以区分二者，但通过统计足的数目，科学家们就能根据奇偶性判断出千足虫所属的星球。  作为 J 国派去 NASA 的秘密间谍，你希望参加这次研究活动以掌握进一步的情报，而 NASA 选拔的研究人员都是最优秀的科学家。于是 NASA 局长 Charles Bolden 出了一道难题来检测你的实力： 现在你面前摆有 $1\ldots N$ 编号的 $N$ 只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。 Charles 每次会在这 $N$ 只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数 $\bmod$ $2$ 的结果反馈给你，同时告诉你一开始放入机器中的是哪几只虫子。 他的这种统计操作总共进行 $M$ 次，而你应当尽早得出鉴定结果。  假如在第 $K$ 次统计结束后，现有数据就足以确定每只虫子的身份，你就还应将这个 $K$ 反馈给 Charles，此时若 $K

无

无

### 评分标准 对于每一个测试点，如果你的输出文件与答案文件完全相同，该测试点得满分。 否则，对于存在唯一解的测试点，如果你正确回答所有千足虫的身份，将得到 $50\%$ 的分数； 其他情况，该测试点得零分。 ### 数据规模和约定 对于 $20\%$ 的数据，满足 $N=M\leq 20$； 对于 $40\%$ 的数据，满足 $N=M\leq 500$； 对于 $70\%$ 的数据，满足 $N\leq500$，$M\leq 10^3$； 对于 $100\%$ 的数据，满足 $1\leq N\leq 10^3$，$1\leq M\leq 2\times 10^3$。