#P18658. LaLa and Divination Magic

    ID: 17994 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-2-SAT蕴含图位集求交传递闭包位集求并回溯搜索

LaLa and Divination Magic

LaLa and Divination Magic

题目描述

LaLa 擅长占卜魔法。

她希望预测 MM 个事件 E0,E1,…,EM−1E_0,E_1,\ldots,E_{M-1}。每个事件只有两种结果:灾难或救赎。

每施展一次占卜魔法,LaLa 会得到下面四种形式之一的知识:

  1. Knowledge⁡(i,j,1)\operatorname{Knowledge}(i,j,1):EiE_i 的结果是灾难,或者 EjE_j 的结果是灾难,也可能两者都是灾难。
  2. Knowledge⁡(i,j,2)\operatorname{Knowledge}(i,j,2):EiE_i 的结果是救赎,或者 EjE_j 的结果是灾难,也可能两者都成立。
  3. Knowledge⁡(i,j,3)\operatorname{Knowledge}(i,j,3):EiE_i 的结果是灾难,或者 EjE_j 的结果是救赎,也可能两者都成立。
  4. Knowledge⁡(i,j,4)\operatorname{Knowledge}(i,j,4):EiE_i 的结果是救赎,或者 EjE_j 的结果是救赎,也可能两者都是救赎。

LaLa 施展了若干次魔法,也可能一次都没有施展。她写下了与得到的所有知识同时相容的全部事件结果,也就是所有满足这些知识的 MM 元组。这个集合称为占卜结果。然后,LaLa 睡着了。

醒来后,LaLa 发现她的宠物 Leo 弄坏了魔法所给出的预测。她找回了占卜结果,但不确定这些数据是否也被 Leo 弄坏了。

给定她找回的占卜结果,请判断是否存在一组知识,使其允许的所有结果恰好是给定集合;如果存在,输出任意一组这样的知识。

用二进制表示结果:00 表示灾难,11 表示救赎。注意,只让给定的每个结果都满足输出知识还不够;输出知识不能允许任何额外结果。

输入格式

输入一组数据。

第一行包含两个整数 N,MN,M,分别表示找回的结果数量、事件数量。

接下来 NN 行,每行是一个长度为 MM 的二进制字符串 SiS_i。其中第 jj 个字符为 1 当且仅当该结果中事件 EjE_j 得到救赎。

数据范围

  • N,MN,M 是整数,1≤N,M≤20001\le N,M\le2000。
  • 每个 SiS_i 的长度为 MM,仅包含 0 和 1。
  • 所有字符串两两不同。
  • 事件下标从 00 到 M−1M-1。

输出格式

如果不存在符合要求的知识集合,输出一个整数 −1-1。

否则,第一行输出一个整数 KK,表示知识数量;接下来 KK 行,每行输出三个整数 Ii,Ji,tiI_i,J_i,t_i,表示一条知识 Knowledge⁡(Ii,Ji,ti)\operatorname{Knowledge}(I_i,J_i,t_i)。

要求 0≤K≤2M20\le K\le2M^2,事件下标在 [0,M−1][0,M-1] 内,知识类型在 [1,4][1,4] 内。两个事件下标可以相同。可以证明,只要存在符合要求的知识集合,就存在一组满足上述数量限制的知识。

答案可能不唯一,输出任意一组即可。K=0K=0 表示没有任何知识约束。

样例输入 1

2 1
1
0

样例输出 1

0

样例输入 2

3 3
101
011
111

样例输出 2

6
0 2 3
0 1 4
0 2 4
1 2 3
1 2 4
2 2 4