#4441. 「202503三级」分玩具 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

已知 n 位小朋友对 m 件玩具的喜好(n ≤ m),现要将 m 件玩具分给 n 位小朋友,每位小朋友只能分到 1 件玩具,每件玩具也最多只能分给 1 位小朋友,并且还要求每位小朋友都能分到自己喜欢的玩具。 本题请你对任意 n 和 m 尝试列出所有满足要求的方案。

输入格式

输入第一行给出两个正整数 n 和 m(n ≤ m ≤ 8),即小朋友人数和玩具的数量。 随后 n 行,每行给出 m 个数字。其中第 i 行第 j 个数字为 1 表示第 i 位小朋友喜欢第 j 件玩具,为 0 则表示不喜欢。

输出格式

按升序列出所有满足要求的方案,格式为 (s1, … , sn)。其中 si 表示第 i 位小朋友分到了第 si 件玩具。 注:方案 (a1, … , an) < (b1, … , bn) 是指存在 1 ≤ k ≤ n,使得 ai = bi 对所有 1 ≤ i< k 成立,并且有 ak < bk。

样例

样例输入

复制4 5
0 1 0 0 1
1 1 0 1 0
1 0 1 1 0
0 0 0 1 1

样例输出

复制(2, 1, 3, 4)
(2, 1, 3, 5)
(2, 1, 4, 5)
(2, 4, 1, 5)
(2, 4, 3, 5)
(5, 1, 3, 4)
(5, 2, 1, 4)
(5, 2, 3, 4)