加密网络

Time Limit: 1000MS

Memory Limit: 131072KB

Description

某军事科研机构在内部搭建了局域网,由于军事科研项目的特殊性,网络通讯之间的保密协议成为了一个重要课题。

该机构的网络技术人员开发出这样一套方案来构建网络:

该网络中一共有N台电脑,每台电脑都视为一个计算机结点。

两台计算机之间若需要通讯,则在两台计算机之间直接建立通讯线路;这样数据不经过别的计算机转发,可以保证数据不会被中途监听,两台计算机之间可能存在多条通讯线路,一台计算机不会与自己有一条通讯线路。

技术人员把网络中的计算机分为两种:把长期保存涉密信息的电脑成为涉密计算机,而辅助涉密计算机进行大型运算的机器成为工作计算机。

网络中每台计算机在运行都有一个加密系数(非负整型)。对于每台涉密计算机设一个固定的加密系数,由技术人员统一分配;对于每台工作计算机,在工作时随机生成一个加密系数。

在两台加密系数分别为X和Y的计算机进行通信时,该网络的通讯协议要求通信数据进行加密,加密方法为:X与Y进行异或,其结果为Z,生成一个长度为Z的通讯校验码,校验码的内容与日期和通讯计算机的加密系数有关。

虽然上述机制在很大程度上保证了数据的保密,但是在需要大量计算机协同工作时,通讯校验码过长会影响科研计算的效率。于是在有重大科研项目计算时,技术人员通过人工分配工作计算机加密系数的方法,使得网络中所有通讯线路的通讯校验码的长度之和最短。

给你网络中计算机与通讯线路的信息,并给你所有涉密计算机的加密系数,现在技术人员想知道:通过分配工作计算机加密系数,所有通讯线路的通讯校验码的长度之和的最小值是多少。这个任务就交给你来完成

Input

多组样例输入,对于每一组样例:

第一行两个整数N( <=500 )和M( <=2500 ),表示计算机节点数与通信线路数

接下来M行,每行两个整数U,V,表示一条通信线路相互通信的两个结点编号

之后一行,包含一个整数P( <=N ),表示已经获得加密系数的计算机节点数

接下来P行,每行两个整数V与W,涉密计算机结点的序号与该结点的加密系数X

Output

一个整数,即所有线路最小的通讯校验码长度之和

Sample Input

3 2
1 3
3 2
2
1 100
2 5

Sample Output

97

Hint

None

Source

None

提交代码