诗句重建

题目描述

两位诗人各自留下了一段诗句，分别记为字符串 $A$ 与 $B$。学者希望从中找出一段共同的诗意，也就是它们的最长公共子序列。

请你：

1. 计算最长公共子序列的长度；
2. 输出满足该长度的字典序最小的公共子序列字符串。

输入格式

输入共两行。

• 第一行是字符串 $A$。
• 第二行是字符串 $B$。

字符串仅包含小写英文字母。

输出格式

输出两行。

• 第一行输出一个整数，表示最长公共子序列的长度。
• 第二行输出该长度的字典序最小的公共子序列字符串。

输入输出样例 #1

输入 #1

abcbdab
bdcaba

输出 #1

4
bcab

数据范围

对于所有测试数据，保证：

• $1 \le |A|,|B| \le 1000$。