Valley Numer II

Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

众所周知,度度熊非常喜欢图。

它最近发现了图中也是可以出现 valley —— 山谷的,像下面这张图。




为了形成山谷,首先要将一个图的顶点标记为高点或者低点。标记完成后如果一个顶点三元组<X, Y, Z>中,X和Y之间有边,Y与Z之间也有边,同时X和Z是高点,Y是低点,那么它们就构成一个valley。

度度熊想知道一个无向图中最多可以构成多少个valley,一个顶点最多只能出现在一个valley中。

Input

第一行为T,表示输入数据组数。

每组数据的第一行包含三个整数N,M,K,分别表示顶点个数,边的个数,标记为高点的顶点个数。

接着的M行,每行包含两个两个整数Xi,Yi,表示一条无向边。

最后一行包含K个整数Vi,表示这些点被标记为高点,其他点则都为低点。

● 1≤T≤20

● 1≤N≤30

● 1≤M≤N*(N-1)/2

● 0≤K≤min(N,15)

● 1≤Xi, Yi≤N, Xi!=Yi

● 1≤Vi≤N

Output

对每组数据输出最多能构成的valley数目。

Sample Input

3 3 2 2 1 2 1 3 2 3 3 2 2 1 2 1 3 1 2 7 6 5 1 2 1 3 1 4 2 3 2 6 2 7 3 4 5 6 7

Sample Output

1 0 2

Hint

Source

2017百度之星程序设计大赛 - 复赛

提交代码