题目描述

题目译自 CEOI2013 Day1 T3「Splot」

亚得里亚海的海岸线和岛屿拥有各种形状和大小的迷人海滩。然而，许多海滩无法通过汽车到达。为了满足日益增长的需求，海岸附近的一大片场地被改建成了停车场。由于所有参与设计的建筑师都有电气工程背景，停车场的布局类似于设计电路时常用的串并联图。

停车场由停车位和连接它们的双向道路组成。每条道路连接两个不同的停车位，且每对停车位之间最多只有一条道路。任何时候，每个停车位最多只能停放一辆车。其他车辆不能通过被占用的停车位行驶。

串并联停车场（splot）是指具有两个特殊停车位源点和终点的停车场，通过串联和并联组合规则从单个停车位构建而成。每个串并联停车场可以通过其编码来指定：这是一系列描述其结构和停车情况的字符。有效的串并联停车场及其编码递归地定义如下：

1. 由单个停车位和无道路组成的停车场是一个有效的串并联停车场。这个单一的停车位既是串并联停车场的源点也是终点。如果停车位为空，其编码为小写字母 $\texttt{o}$；如果停车位被车辆占用，其编码为小写字母 $\texttt{x}$。
2. 如果 $G_{1}$ 和 $G_{2}$ 是两个有效的串并联停车场，那么它们的串联组合 $G$ 也是一个有效的串并联停车场。串联组合是通过在 $G_{1}$ 的终点和 $G_{2}$ 的源点之间添加一条道路来实现的。新得到的串并联停车场 $G$ 的源点是 $G_{1}$ 的源点，终点是 $G_{2}$ 的终点。如果 $E_{1}$ 和 $E_{2}$ 分别是串并联停车场 $G_{1}$ 和 $G_{2}$ 的编码，则 $G$ 的编码为 \texttt{S}E_{1}E_{2}\texttt{#}。换句话说，编码由大写字母 $\texttt{S}$、被组合的串并联停车场的编码以及井号 \texttt{#} 连接而成。
3. 如果 $G_{1}$ 和 $G_{2}$ 是两个有效的串并联停车场，那么它们的并联组合 $G$ 也是一个有效的串并联停车场。并联组合是通过添加两个新的停车位 $s$ 和 $t$，以及连接 $s$ 与 $G_{1}$ 和 $G_{2}$ 的源点的道路，以及连接 $t$ 与 $G_{1}$ 和 $G_{2}$ 的终点的道路来实现的。新得到的串并联停车场 $G$ 的源点是新添加的停车位 $s$，终点是新添加的停车位 $t$。如果 $E_{1}$ 和 $E_{2}$ 分别是串并联停车场 $G_{1}$ 和 $G_{2}$ 的编码，$E_{s}$ 和 $E_{t}$ 是源点 $s$ 和终点 $t$ 的编码（如果对应的停车位为空则为小写字母 $\texttt{o}$，否则为小写字母 $\texttt{x}$），则 $G$ 的编码为 \texttt{P}E_{s}|E_{1} E_{2}|E_{t} \texttt{#}。换句话说，编码由大写字母 $\texttt{P}$、源停车位的编码、竖线 $\texttt{|}$、被组合的串并联停车场的编码、另一竖线 $\texttt{|}$、终点停车位的编码以及井号 \texttt{#} 连接而成。

例如，上图中串并联停车场的编码为 \texttt{Po|Px|Sxo#Soo#|O#Soo#|O#}。注意，串并联停车场 $G$ 的编码中小写字母的数量始终与 $G$ 中的停车位数量相同，并且 $G$ 中的停车位与其编码中的小写字母一一对应。

停车场只有一个出口，直接连接到整体串并联停车场的源停车位。我们称一辆车未被阻挡，如果它可以通过某条道路和空闲停车位的序列到达出口，即源停车位。例如，在上述串并联停车场中，两个车辆都未被阻挡；但如果在串并联停车场的终点停车位（最右边的节点）停车一辆车，那么其中一辆车将会被阻挡。允许在串并联停车场的源停车位停车，但如果这样做，串并联停车场中所有其他车辆将会被阻挡。

停车场的运营者希望以一种不阻挡任何车辆的方式安排进场车辆。假设我们得到一个可能已经有一些车辆的串并联停车场，但这些车辆都未被阻挡。请编写一个程序，计算在不阻挡任何车辆且不移动现有车辆的情况下，能够停放的最大车辆总数（包括已停放的车辆）。此外，您的程序还应找到一种安排这种最大车辆数量的方法。

输入格式

输入的第一行包含一个字符序列，表示给定串并联停车场的编码。序列中只会出现大写字母 $\texttt{P}$ 和 $\texttt{S}$、小写字母 $\texttt{o}$ 和 $\texttt{x}$、以及字符 \texttt{#} 和 $\texttt{|}$。输入将是根据上述规则编码的串并联停车场。串并联停车场中已有的车辆不会被阻挡。

输出格式

输出应包含两行。第一行应包含一个整数 $M$，表示在上述条件下能够停放的最大车辆数。第二行应包含一个字符序列， 表示最优车辆安排后的串并联停车场编码。该序列应恰好包含 $M$ 个 $\texttt{x}$ 字符，并且可以通过将输入序列中的部分 $\texttt{o}$ 替换为 $\texttt{x}$ 获得。可能存在多种最优安排，您的程序可以输出其中任意一种。

Po|Px|Sxo#Soo#|o#Soo#|o#

3
Po|Px|Sxo#Sox#|o#Soo#|o#

数据范围与提示

如果输出的方案不正确，但输出的第一行（最大车辆数）是正确的，该解答将获得对应测试点 $80\%$ 的分数。

• 对于 $30\%$ 的数据，串并联停车场中的停车位总数最多为 $20$ 个。
• 对于 $40\%$ 的数据，串并联停车场为空，即输入中不包含字母 $\texttt{x}$。
• 对于 $100\%$ 的数据，串并联停车场的编码长度至少为 $1$ 且至多为 $10^5$。