← 返回题目列表

Codeforces · 612/C

C. 替换以形成常规括号序列

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

给定的字符串 s 由四种左括号和右括号组成:<>、{}、[]、()。有两种类型的括号:开括号和闭括号。您可以用另一个相同类型的支架替换任何支架。例如,您可以将 < 替换为括号 {,但不能将其替换为 ) 或 >。

下面的正则括号序列的定义是众所周知的,因此您可以熟悉它。

让我们定义一个常规括号序列(RBS)。空字符串是 RBS。令 s1 和 s2 为 RBS,则字符串 <s1>s2、{s1}s2、[s1]s2、(s1)s2 也是 RBS。

例如,字符串“[[(){}]<>]”是 RBS,但字符串“[)()”和“][()()”不是。

确定使字符串成为 RBS 的最少替换次数。

输入

唯一一行包含一个非空字符串 s,仅由四种左右括号组成。 s的长度不超过106。

输出

如果不可能从 s print 获得 RBS 则不可能。

否则打印从 s 获取 RBS 所需的最少替换次数。

示例

输入 #1

[<}){}

输出 #1

2

输入 #2

{()}[]

输出 #2

0

输入 #3

]]

输出 #3

Impossible