题目描述

一个给定序列的子序列是在该序列中删除若干元素得到的序列。若给定序列 \(X=\{x_1,x_2,…,x_m\}\) ，则另一序列 \(Z=\{z_1,z_2,…,z_k\}\) 是 \(X\) 的子序列是指存在一个严格递增的下标序列 \(\{i_1,i_2,…,i_k\}\) 使得对于所有 \(j=1,2,…,k\) 有：\(z_j=x_{ij}\)。例如，序列 \(Z=\{B,C,D,B\}\) 是序列 \(X=\{A,B,C,B,D,A,B\}\) 的子序列，相应的递增下标序列为 \(\{2,3,5,7\}\)。给定 \(2\) 个序列 \(X\) 和 \(Y\)，当另一序列 \(Z\) 既是 \(X\) 的子序列又是 \(Y\) 的子序列时，称 \(Z\) 是序列 \(X\) 和 \(Y\) 的公共子序列。例如，若 \(X=\{A,B,C,B,D,A,B\}\)，\(Y=\{B,D,C,A,B,A\}\)，则序列 \(\{B,C,A\}\) 是 \(X\) 和 \(Y\) 的一个公共子序列，序列 \(\{B,C,B,A\}\) 也是 \(X\) 和 \(Y\) 的一个公共子序列。而且，后者是 \(X\) 和 \(Y\) 的一个最长公共子序列，因为 \(X\) 和 \(Y\) 没有长度大于 \(4\) 的公共子序列。
给定 \(2\) 个序列 \(X=\{x_1,x_2,…,x_m\}\) 和 \(Y=\{y_1,y_2,…,y_n\}\)，找出\(X\)和\(Y\)的一个最长公共子序列。

格式

输入格式

输入共有两行，每行为一个由字母构成的长度不超过 \(2000\) 的字符串，表示序列 \(X\) 和 \(Y\)。

输出格式

输出第一行为一个非负整数，表示所求的最长公共子序列的长度，若不存在公共子序列，则输出仅有一行输出一个整数\(0\)，否则在输出的第二行输出所求得的最长公共子序列，若满足条件的最长公共子序列不止一个，只需输出其中任意一个。

样例1

样例输入1

ABCBDAB
BDCABA

样例输出1

4
BCBA

限制

\(100\%\) 的数据：序列长度不超过\(2000\)。