已知 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
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)
(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)