Background: You are given two DNA sequences, sequence$1$

with size n characters and sequence$2$ with m characters. DNA sequences are composed

of the characters $$A$,$C$,$G$,$ and $$T$.$ Each DNA sequence may contain two consecutive

sequences: sequence$1=$sequence$11+$sequence$12$ and sequence$2=$sequence$21+$sequence$22.$

For example, sequence$1=$AGACTACCG$,$ sequence$1$ may contain two consecutive se$-$

quences sequence$11=$ and sequence$12=$AGACTACCG$,$ or sequence$1$ may contain two

sequences sequence$11=$A$$ and sequence$12=$GACTACCG$,...$ or sequence$1$ may contain

two sequences sequence$11=$AGACTACCG$$ and sequence$12=.$

Your task is to find two sequences, sequence$12$ and sequence$22,$ such that: $(1)$ The

length of the longest common subsequence $($LCS$)$ of sequence$12$ and sequence$22$ is equal

to the length of the LCS of sequence$1$ and sequence$2.(2)$ The total number of characters

in sequence$12$ and sequence$22$ is minimized. The output should be the length of the LCS

and the total length of the two sequences, sequence$12$ and sequence$22,$ that you have

found.

An O$($nm$)-$time algorithm is su$$ce to pass any feasible test cases.

Hint: use the dynamic programming algorithm for longest common subsequence prob$-$

lem.

$($a$)$ Input You need to read the input from the console. It contains two lines, each

containing one sequence. In the first line of the input, we have n characters; and in

the second line of the input, we have m characters. You can assume that $1$ n $$

$10000$ and $1$ m $10000.$

$($b$)$ Output You need to output to the console. The first line is an integer indicating

the length of the LCS between the given two sequences. The second line is the total

length of the two sequences, sequence$12$ and sequence$22.$