1821 - 最长公共子序列(LCS)(1)

1821 - 最长公共子序列(LCS)(1)

链接：1821 - 最长公共子序列(LCS)(1)-东方博宜OJ

1821 - 最长公共子序列(LCS)(1)

题目描述

给出 1∼n1∼n 的两个排列 P1P1​ 和 P2P2​ ，求它们的最长公共子序列。

输入

第一行是一个数 nn ；（ nn 是 5∼10005∼1000 之间的整数）

接下来两行，每行为 nn 个数，为自然数 1∼n1∼n 的一个排列（1∼n1∼n 的排列每行的数据都是 1∼n1∼n 之间的数，但顺序可能不同，比如 1∼51∼5 的排列可以是：11 22 33 44 55 ，也可以是 22 55 44 33 11 ）。

输出

一个整数，即最长公共子序列的长度。

样例

输入

复制