#2771. YY的Train

题目描述

YY在学会了Treap之后更加努力了，于是乎他的灵魂穿越了时空到达了3838年3月8日参加了第38届UOI，凭借着快速转换农历和阴历的能力，他拿到了金牌第38名。功成名就之后友爱的YY小朋友终于当上了火车调度员。现在小YY面临着一个难题，如何把湘江东岸的粮食运到湘江西岸去。湘江沿岸总共有N个火车站，这N个火车站由M条双向铁路连接，并且保证 任意两个站点可以互达 。湘江东岸有east个火车站，湘江西岸有west个火车站（ 当然可能有站点设置在江中 ），其中东岸有P个火车站中停留了一列装满粮食的火车。YY的任务是合理安排让这P列火车停在P个 不同的 西岸站点。每条铁路通过的时间都是一天，当然铁路部门为了保证安全要求每一天一条铁路只能通过一列火车。火车在到达目标之前可以在任意站点停留任意天，每个站点最多可以停留P列火车。上级部门要求YY拿出一套方案使得最晚到达的火车尽早到达。当然YY作为UOI金牌有更加重要的事情（要和Daren Nicholas打篮球啦，要和Luciano踢足球啦）所以这个任务就交给你啦。注意：编号为1到east的是东边的火车站，编号为n- west+1到n的是西边的火车站

输入格式

第一行四个整数N,M,east,west

接下来M行每行两个整数u,v描述一条连通u,v的铁路

倒数第二行一个整数P

最后一行P个整数，表示P列火车停留的地方

输出格式

一个整数，表示最晚达到的火车达到的时间。

样例

样例输入

2 1 1 1  

1 2  

1  

1

样例输出

1  

数据范围与提示

n<=10^6,m=n-1,且保证存在一个站点将东岸和西岸的站点分开

此题为OJ2077