406189: GYM102307 C Common Subsequence

Manuel thinks that Diego is his long lost brother. But Diego thinks Manuel is wrong, and to prove it, he got DNA samples from himself and Manuel. Now Diego has given you the DNA samples and it is your task to say whether they are brothers or not.

The DNA samples of Diego and Manuel are strings $$$A$$$ and $$$B$$$, both have length $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and consist of only the characters 'A', 'T', 'G' and 'C'. If there is a common subsequence of $$$A$$$ and $$$B$$$ that has length greater than or equal to $$$0.99 \times n$$$, then Diego and Manuel are brothers, in other case, they are not.

The input consists of two lines with strings $$$A$$$ and $$$B$$$, respectively.

You should output a single line with "Long lost brothers D:" (without quotes) if Diego and Manuel are brothers, and "Not brothers :(" (without quotes) if they are not.

GAATTGCGTACAATGC
GAATTGCGTACAATGC

Long lost brothers D:

CCATAGAGAA
CGATAGAGAA

Not brothers :(

A subsequence of a string $$$X$$$ is any string that you can get by removing any number of characters from $$$X$$$.

A common subsequence of strings $$$X$$$ and $$$Y$$$ is a string that is a subsequence of both $$$X$$$ and $$$Y$$$.