Longest Common Palindromic Subsequence

Given two sequences of positive integers

\(X=(x_1, x_2, \cdots, x_m)\) and \(Y=(y_1, y_2, \cdots, y_n)\), a common subsequence is a sequence \( (x_{i_1}, x_{i_2}, \cdots, x_{i_t}) \) such that there exists indices \(j_1, j_2, \cdots, j_t\) with \(x_{i_k}=y_{j_k}\) and \(i_1 < i_2 < \cdots < i_t\). A sequence is called a palindrome if it reads the same forward and backward. For example, \((1,3,5,3,1)\) is a palindrome.

A common palindromic subsequence of X and Y is a sequence that is both a common subsequence and a palindrome. Among all such subsequences, the one with the maximum length is called a longest common palindromic subsequence. Note that there may be multiple longest common palindromic subsequences. For example, if \(X=(1,9,3,9,1)\) and \(Y=(1,3,9,3,1)\), both \((1,3,1)\) and \((1,9,1)\) are longest common palindromic subsequences.

Your task is: Given two sequences X and Y, determine the length of their longest common palindromic subsequence.

Input format note: The first line contains two integers \(m\) and \(n\), representing the lengths of X and Y respectively. The second line contains \(m\) positive integers representing X, and the third line contains \(n\) positive integers representing Y.

inputFormat

The first line contains two integers \(m\) and \(n\).
The second line contains \(m\) positive integers representing the sequence X.
The third line contains \(n\) positive integers representing the sequence Y.

outputFormat

Output a single integer denoting the length of the longest common palindromic subsequence of X and Y.

sample

5 5
1 9 3 9 1
1 3 9 3 1

3