← 返回题目列表

Codeforces · 2144/F

F. 支架组

中文机器翻译题面 查看原题

正则括号序列是可以变换为正确的算术序列的括号序列。例如:

  • 括号序列“()()“和”(())" 是正则表达式(结果表达式是: "(1)+(1)“和”((1+1)+1)");
  • 括号序列“)(", "(“和”)“不是。

给你 $$$n$$$ 括号序列 $$$s_1, s_2, \dots, s_n$$$ (不一定是正则)和偶数 $$$k$$$。您的任务是将它们全部分成几组,方式如下:

  • 每个括号序列都属于一组;
  • 对于每个组,都存在一个 常规 长度恰好为 $$$k$$$ 的括号序列,使得分配给该组的每个括号序列是 不是子字符串 它。

可以实现的最小组数是多少?如果对于任意数量的组都无法做到这一点,请报告。否则,打印组以及每个组的任何有效的常规括号序列。如果组数最少有多个答案,则打印其中任何一个。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$;$$$2 \le k \le 50$$$;$$$k$$$ 是偶数)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含括号序列 $$$s_i$$$ ($$$2 \le |s_i| \le k$$$)。它仅由字符 ' 组成(' 和 ')'.

输出

如果无法按照规则将所有括号序列分组,则打印$$$-1$$$。

否则,在第一行打印尽可能小的组数$$$m$$$。然后,$$$m$$$ 数据块应该如下:

  • 每个块的第一行应包含长度为 $$$k$$$ 的常规括号序列。
  • 第二行应包含一个整数 $$$g$$$ — 当前组中括号序列的数量。
  • 第三行应包含从 $$$1$$$ 到 $$$n$$$ 的 $$$g$$$ 整数 - 属于当前组的括号序列的索引。

这些括号序列都不应该是所选常规括号序列的子字符串。从 $$$1$$$ 到 $$$n$$$ 的每个索引都应该属于一组。

如果存在多个最小 $$$m$$$ 的答案,请打印其中任何一个。

示例

输入
复制

3 6
)))
(((
(())

输出
复制

1
(()())
3
1 2 3

输入
复制

4 6
(()
()(
())
((((((

输出
复制

2
(())()
1
2
()()()
3
1 4 3

输入
复制

2 6
()
)(

输出
复制

-1