YY的Train

时间限制:10s      空间限制:128MB

题目描述

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踢足球啦)所以这个任务就交给你啦。
 


输入格式

第一行四个整数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,且保证存在一个站点将东岸和西岸的站点分开
 


题目来源

没有写明来源