/*
首先，dp的最开始是定义状态 dp[i][j] 表示A串的前i个，与B串的前j个，并以B[j]为结尾的LCIS 的长度.
状态转移方程：
if(A[i]==B[j]) dp[i][j]=max(dp[i-1][k])+1; ( 1 <= k < j )
else dp[i][j]=dp[i-1][j];
然后选择循环顺序，就可以将算法的复杂度降为n*n.
转自:http://www.cnblogs.com/chenhuan001/archive/2013/03/26/2982677.html
PS:用一维数组来记录路径老是wa，测了好多组都是对的，从昨晚一直纠结到现在，先mark，以后看，真想砸电脑*/ #include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define N 550
struct node
{
int x,y;
}path[N][N];
int dp[N][N];
int s[N],t[N]; int main()
{
int t1;
while(scanf("%d",&t1)!=EOF)
{
while(t1--)
{
memset(path,,sizeof(path));
int n,m;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&s[i]);
scanf("%d",&m);
for(int i=;i<=m;i++)
scanf("%d",&t[i]);
memset(dp,,sizeof(dp));
int mx=;
for(int i=;i<=n;i++)
{
mx=;
int tx=,ty=;
for(int j=;j<=m;j++)
{
dp[i][j] = dp[i-][j];
path[i][j].x=i-;
path[i][j].y=j;
if( s[i]>t[j] && mx<dp[i-][j])
{
mx=dp[i-][j];
tx=i-;//修改最长匹配的下标
ty=j;//修改最长匹配的下标
}
if( s[i] == t[j] )
{
dp[i][j]=mx+;
path[i][j].x=tx;//记录前一个匹配的下标
path[i][j].y=ty;//记录前一个匹配的下标
}
}
}
mx=-;
int id;
for(int i=;i<=m;i++)
if(dp[n][i]>mx)
{
mx=dp[n][i];
id=i;
}
int save[N];
int cnt=;
int tx,ty;
tx=n; ty=id;
while( dp[tx][ty] != )
{
int tmpx,tmpy;
tmpx=path[tx][ty].x;
tmpy=path[tx][ty].y;
if(dp[tx][ty]!=dp[tmpx][tmpy])
{
save[cnt++]=t[ty];
}
tx=tmpx; ty=tmpy;
}
printf("%d\n",mx);
for(int i=cnt-;i>=;i--)
printf("%d ",save[i]);
printf("\n");
}
}
return ;
}