OI题库

【问题描述】

狙击手在战争中起着重要作用。他们在战争中击杀远距离敌人。一个狙击小队能抵挡住上百名步兵。在战争中，指挥官必须把他们放在重要的位置上。
今天你是指挥官。敌人正在接近中。你必须派出你的狙击手去阻止他们。这里有N+1个位置，它们以0，1...N来鉴别。敌军从0号位出发。他们的目的地是N号位。如果两个位置是“连接”的，那么他们便可以从一个位置到另一个位置。你在N号位并且不想让任何敌军靠近你。狙击兵只能在1，2...N-1号位。
对于位置i（0＜i＜n），如果这里有不少于ki（0

【输入格式】

第一行有一个整数表示数据个数。
对于每组数据，第一行有两个整数N和M（0＜n<=50，0≤m≤200）。下一行有n-1个整数。它们是k1,k2...kn-1。后面有m行，每行包含一对整数a和b（0≤a，b≤n），意思是a号位与b号位连接。两组数据间没有空行。(n≤50，0≤m≤200）。下一行有n-1个整数。它们是k1,k2...kn-1。后面有m行，每行包含一对整数a和b（0≤a，b≤n），意思是a号位与b号位连接。两组数据间没有空行。n≤50，0≤m≤200）。下一行有n-1个整数。它们是k1,k2...kn-1。后面有m行，每行包含一对整数a和b（0≤a，b≤n），意思是a号位与b号位连接。两组数据间没有空行。(n≤50，0≤m≤200）。下一行有n-1个整数。它们是k1,k2...kn-1。后面有m行，每行包含一对整数a和b（0≤a，b≤n），意思是a号位与b号位连接。两组数据间没有空行。

【输出格式】

对于每组数据，输出最少需要多少个狙击兵，一个数一行。两组数据间没有空行。

【输入样例】

输入文件名： snipers.in

1
4 5
2 3 4
0 1
0 3
1 2
2 4
3 4

输出文件名： snipers.out

6