Glory and LCS-j9国际

1233: Glory and LCS

时间限制: 1000 ms  内存限制: 128 MB
提交: 269  解决: 67
[提交][状态][讨论版]

题目描述

大家都知道，Glory 不但知识水平高，并且非常喜欢思考，有一天 Glory 在思考一个问题，他在纸上写了两个 $1$ 到 $n$ 的排列，并且他想知道这两个排列的最大公共子序列的长度是多少，当然像 Glory 这么优秀的人当然一眼就看出了这个题目的答案，但是他太忙了，不想打这个代码，于是他扔给了他的小弟，但是他的小弟知识水平不够，所以他想找你萌帮帮他，你萌能帮他解决这个问题吗。

输入

第一行一个数 $T$，表示数据的测试组数 ( $T\le 5$ )

每组数据一个 $n$，表示排列的长度 ( $1\le n \le 10^5$ )

接下来两行，每行一个 $1-n$ 的排列

输出

对于每组数据，输出一个数表示最长公共子序列的长度。

样例输入

2
2
1 2
1 2
3
1 3 2
2 3 1

样例输出

2
1

提示

来源

不愿意写标程和数据的Glory

[提交][状态][讨论版]