1094. 一鸣师姐与括号序列

一鸣师姐有 n 个仅由括号组成的字符串 s_1,s_2,s_3,...,s_n,由于一鸣师姐忙着炒股没有时间,所以想请你帮忙重新排列这些字符串,使得将这些字符串首尾相接后能形成一个合法的括号序列。一鸣师姐希望你不要倒置或修改给定的字符串,不要重复使用或者不使用某个字符串。

一鸣师姐认为:

  • 空串是一个合法的括号序列。
  • 如果字符串 A 是一个合法的括号序列,那么字符串 (A) 也是一个合法的括号序列。
  • 如果字符串 AB 都是一个合法的括号序列,那么字符串 AB 也是一个合法的括号序列。

例如 ()()(()) 是一个合法的括号序列,但 ()())()( 不是。

输入

由于测试点较多,为了避免超时代码评测时间过长,本题设置了若干子任务。

子任务设置并无实际意义,请以通过所有测试点为目标。

输入包括若干行。

1 行包含一个整数 n \ (1 \leq n \leq 10^4),表示字符串的数量。

接下来 i 行,每行包含一个仅由括号组成的字符串 s_i \ (1 \leq |s_i| \leq 10^6),含义如题目描述所示。

为方便起见,我们按照输入顺序将第 i 个字符串编号为 i

保证所有字符串长度之和不超过 10^6,即保证 \sum_{i=1}^{n}|s_i| \leq 10^6

输出

如果将所有字符串重新排列后可以形成一个合法的括号序列,输出 2 行:

1 行输出 YES

2 行输出 n 个由空格间隔的整数 p_1,p_2,p_3,...,p_n,表示字符串的排列方式。其中,p_i 是字符串的编号,你需要保证通过按照从左往右的顺序首尾拼接这些编号对应的字符串可以得到一个合法的括号序列。

如果可行的排列方式有多个,输出任意一个即可。

如果无论如何排列都无法形成一个合法的括号序列,直接输出 NO

样例

标准输入 复制文本
3
()
(()
)
标准输出 复制文本
YES
2 1 3
标准输入 复制文本
2
()
))((
标准输出 复制文本
NO

提示

样例 1 中,编号为 2 的字符串为 ((),编号为 1 的字符串为 (),编号为 3 的字符串为 )。按照 2,1,3 的顺序首尾拼接在一起是 (()()),显然是一个合法的括号序列。

样例 2 中,显然无法通过重新排列得到合法的括号序列。

来源

2020 软件学院 AK 杯程序设计竞赛

单点时限 2 秒
内存限制 256 MB
提交 241
通过 44