TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7275
  • 题目
  • P7275用魔法生成回文序列
    限制 : 时间限制 : - MS   空间限制 : - KB
    问题描述

    小Z上英语课思考数学问题被英语老师发现啦~ 英语老师:「你这么爱胡思乱想我问你一道英语题吧」 小Z想跑,但是已经来不及了。 英语老师:「我们定义一个回文串是正方读起来相同的字符串」 小Z:「这个简单,不就是像 "abba" "aba"这样的吗」 英语老师: 「现在给你一个长度为n的字符串,要你求出他的最长回文子序列」 小Z:「子序列是不连续的吧? 好的我知道了」 小Z轻松的解决了这个问题,并把他修改了一下交给你。 现在一个字符串变成了m个数字,会魔法的小Z可以把一个数字x根据变换规 则变成y,给定所有的变换规则,要你求出这个数字串的最长回文子序列。

    输入格式

    第一行输入3个正整数n,k和m,k是转换规则的个数。

    第二行开始的k行,每行两个正整数 x和y,表示数字x可以变成数字y,并且 数字y可以变成数字x。注意,如果数字x可以变成数字y,并且数字y可以变成数字 z,那么数字x也可以便成数字z。x可能等于y,同一对(x, y)可能重复出现。

    最后一行输入m个正整数,表示题目中所提的数字串,每个数≤n。

    输出格式

    输出一行一个数表示答案。

    样例输入

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

    样例输出

    5

    提示

    对于 20% 的数据:n,k,m ≤ 10;

    对于 40% 的数据:n,k,m ≤ 200;

    对于 100% 的数据:n ≤ 105,k ≤ 106,m ≤ 10^3,1 ≤ x,y ≤ n。