Two Subsequences 2

Time limit1sMemory limit128 MB

Summary

Given two strings A and B of length up to 2000, find the shortest string that is a subsequence of A but not a subsequence of B.

Level: Medium6 of 10
Topics: Dynamic programming, String, Greedy
Solved: No attempts yet

Problem

A subsequence of a string A is a non-empty string made by choosing one or more characters from A. The chosen characters must keep their original order in A, but they do not have to be adjacent.

Given two strings A and B, find the shortest string that is a subsequence of A but is not a subsequence of B.

Input

The first line contains string A, and the second line contains string B.

Both strings consist only of lowercase English letters, and each length is at most 2000. Every input is guaranteed to have an answer.

Output

On the first line, print the length of the shortest string that is a subsequence of A but not a subsequence of B.

On the second line, print one such string. If multiple strings are possible, print any one of them.

Examples3

Example 1
Input
```
ababaa
abbaa
```
Expected output
```
3
bab
```
Example 2
Input
```
babab
babba
```
Expected output
```
3
aab
```
Example 3
Input
```
banana
anbnaanbaan
```
Expected output
```
5
banna
```