链接: https://cses.fi/problemset/task/3404

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定两个均为排列的数组，找出它们的最长公共子序列。

子序列是一个可以包含间隔、从左到右的数组元素序列。公共子序列是同时出现在两个数组中的子序列。

输入

第一行包含两个整数 $n$ 和 $m$：两个数组的大小。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$：第一个数组的内容。

第三行包含 $m$ 个整数 $b_1,b_2,\dots,b_m$：第二个数组的内容。

输出

首先输出最长公共子序列的长度。

之后输出一个这样的序列示例。如果有多个解，你可以输出任意一个。

数据范围

$1 \le n,m \le 2 \cdot 10^5$ $1 \le a_i \le n$ $1 \le b_i \le m$

样例输入

8 6
3 1 2 8 5 7 6 4
6 5 1 2 3 4

样例输出

3
1 2 4