TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3082
  • 题目
  • P3082加油站
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    问题描述

    某省有N座城市,这些城市间通过M条双向道路连接起来,使得任意两个城市都可相互到达。每个城市都有两种车,一种使用柴油,一种使用汽油。知名企业家何老板在每座城市都开设了一个加油站,有的加油站只卖汽油,有的加油站只卖柴油,有的加油站两种油都卖。
    最近下了很长一段时间的暴雨,道路有被山洪冲毁的危险。何老板很担心,他想知道,哪些道路毁坏了会使得某个或某些城市的车辆无法加到合适的油,请你计算这样的道路总共有多少条?(两个城市间最多有一条道路直接相连)

    输入格式

    第一行是四个整数N,M,K,L (N是城市数,编号1到N;M是道路条数;K是提供汽油的加油站个数;L是提供柴油的加油站个数)。
    第二行有K个数,每个数表示提供汽油的加油站所在城市的编号。
    第三行有L个数,每个数表示提供柴油的加油站所在城市的编号。
    接下来M行,每行两个不同的整数,表示一道路的起止城市的编号。

    输出格式

    一行,一个整数表示问题的答案。

    样例输入

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

    样例输出

    3

    提示

    【样例解释】
    如下三条路中,任意一条坏掉都会使得有些城市的车辆无法加到合适的油。
    2 3
    5 6
    7 9
    【数据范围】
    1<=N<=100000,
    1<=M<=1000000,
    1<=K<=N
    1<=L<=N


    来源  改编自ceoi2005