Bài toán:

Khi được học về LCS, Tèo rất hứng thú vì học được phương pháp hay, học được cách vận dụng biến đổi các bài toán liên quan về dạng quen thuộc để ứng dụng được LCS và đã giải bài toán như sau:

Cho hai xâu ký tự X và Y, tìm một xâu con có giá trị lớn nhất giữa hai xâu đã cho. Ví dụ ~X = 1003456~ và ~Y = 001435~: Một xâu con chung như "00", "0035", "135", "145", ... Xâu con chung có giá trị lớn nhất là "145". Xâu con chung này có độ dài là 3.

Bạn hãy giúp Tèo viết chương trình tìm xâu con chung có giá trị lớn nhất để Tèo có thể kiểm tra đáp án của mình.

Dữ liệu vào:

• Dòng 1 là xâu ký tự X.
• Dòng 2 là xâu ký tự Y.

Hai xâu chỉ chứa ký tự số. Độ dài mỗi xâu không quá 1000.

Dữ liệu ra:

• In ra dòng 1 là độ dài của xâu con chung lớn nhất cần tìm.
• Dòng thứ hai in ra xâu con chung lớn nhất, nếu không tồn tại xâu con chung thì in -1.

Ví dụ:

Input:

1003456
001435

Output:

3
145