COETEST5

Trong quá trình vận chuyển hàng hóa, thứ tự giao hàng của một đơn hàng sẽ phụ thuộc vào độ ưu tiên của đơn hàng đó. Trong khi giao hàng, các tài xế sẽ phải vạch ra cho mình một lộ trình đường đi giao hàng sao cho đảm bảo các ràng buộc về độ ưu tiên của các đơn hàng không bị vi phạm.

Hình dưới đây mô tả các ràng buộc về độ ưu tiên giữa 6 địa điểm cần giao hàng.

Có tất cả 5 ràng buộc về độ ưu tiên như sau:

1. Địa điểm 5 cần được ưu tiên nhận hàng trước địa điểm 6.
2. Địa điểm 5 cần được ưu tiên nhận hàng trước địa điểm 1.
3. Địa điểm 3 cần được ưu tiên nhận hàng trước địa điểm 6.
4. Địa điểm 2 cần được ưu tiên nhận hàng trước địa điểm 5.
5. Địa điểm 6 cần được ưu tiên nhận hàng trước địa điểm 4.

Lưu ý, địa điểm x cần nhận hàng trước địa điểm y thì không có nghĩa là x phải giao ngay trước y mà x có thể giao trước, sau đó giao đến các địa điểm khác, rồi mới giao đến địa điểm y thì vẫn thỏa mãn địa điểm x đã nhận hàng trước địa điểm y.

• Nếu các địa điểm nhận hàng được giao hàng theo thứ tự 3 2 5 6 4 1, thì dưới đây là một thứ tự đúng, vì tất cả các ràng buộc về ưu tiên đều không bị vi phạm.

• Nếu các địa điểm nhận hàng được giao hàng theo thứ tự 2 5 1 6 4 3, thì với ràng buộc về độ ưu tiên thứ 3 khi địa điểm 3 cần được giao hàng trước địa điểm 6, nhưng với ví dụ này địa điểm thứ 3 nhận hàng sau địa điểm thứ 6, nên đây là một thứ tự sai và có một ràng buộc sai đó là ràng buộc thứ 3.

Cho thông tin các ràng buộc về độ ưu tiên giao hàng của các địa điểm nhận hàng và một thứ tự giao hàng mà các tài xế đã vạch ra, hãy kiểm tra thứ tự giao hàng đó có thỏa mãn tất cả các ràng buộc đã cho hay không? Nếu không thỏa mãn hãy cho biết thứ tự giao hàng đó đã vi phạm bao nhiêu ràng buộc.

[Input]

Dòng đầu tiên là số lượng test case T (T ≤ 50). Thông tin về mỗi test case như sau:

Dòng đầu tiên là gồm hai số nguyên dương N (5 ≤ N ≤ 100) và M (1 ≤ M ≤ (N x (N - 1)) / 2) tương ứng là số địa điểm cần giao hàng N và số ràng buộc M, hai số này phân biệt với nhau bởi một dấu cách.

M dòng tiếp theo mỗi dòng gồm hai số nguyên dương x, y thể hiện một ràng buộc là địa điểm x cần được giao hàng trước địa điểm y, hai số này phân biệt nhau bởi một dấu cách, có giá trị khác nhau và nằm trong đoạn [1,N].

Dòng tiếp theo là một số nguyên dương Q (1 ≤ Q ≤ 10) mô tả số lượng thứ tự giao hàng cần kiểm tra.

Trong Q dòng cuối cùng của mỗi test case, mỗi dòng gồm N số khác nhau có giá trị trong đoạn [1,N], mô tả thứ tự giao hàng cần kiểm tra, hai số cạnh nhau phân biệt với nhau bởi một dấu cách.

Lưu ý:

• Có thể có những địa điểm không có bất kỳ ràng buộc ưu tiên nào.
• Input sẽ không có trường hợp nào mà các điều kiện ràng buộc tạo thành một vòng lặp như ví dụ dưới đây: 5 trước 6, 6 trước 4, 4 trước 1, 1 trước 5, như thế sẽ không tồn tại bất kỳ thứ tự giao hàng nào thỏa mãn tất cả các ràng buộc.

[Output]

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra “#tc”, với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra cho mỗi test case gồm Q số tương ứng với kết quả của Q dãy thứ tự giao hàng cần kiểm tra, Q số này cần được in ra trên cùng một dòng, hau số cạnh nhau phân biệt với nhau bởi một dấu cách, kết quả tương ứng cho mỗi thứ tự giao hàng cần kiểm tra là một trong hai giá trị sau:

• 0 nếu thứ tự đó giao hàng đó thỏa mãn tất cả các ràng buộc.
• k ràng buộc ưu tiên bị vi phạm (1 ≤ k ≤ M)

Example

Input:
5
6 5
5 6
5 1
3 6
2 5
6 4
5
3 2 5 6 4 1 
2 5 1 6 4 3 
3 2 6 5 1 4 
2 5 3 6 4 1 
2 5 1 3 6 4 
10 17
6 3
8 7
2 5
3 4
2 7
9 6
2 9
10 3
8 10
6 5
4 5
8 5
10 9
7 6
1 3
9 7
1 10
7
5 2 8 10 9 7 6 3 4 1 
2 4 9 10 5 7 1 8 3 6 
8 2 1 10 9 7 6 3 4 5 
2 1 8 10 9 7 6 3 4 5 
2 8 1 10 9 7 6 3 4 5 
5 10 3 6 4 8 9 1 7 2 
1 2 8 10 9 7 6 3 4 5 
5 1
2 4
10
5 3 1 2 4 
1 3 2 4 5 
2 5 4 1 3 
1 2 4 3 5 
5 3 1 2 4 
3 5 4 2 1 
1 4 5 2 3 
2 1 4 3 5 
2 1 4 5 3 
5 2 4 1 3 
13 57
13 6
8 11
12 10
8 7
5 11
10 4
4 13
10 5
1 3
5 9
4 7
11 9
5 3
10 6
5 4
1 13
8 10
8 2
13 11
10 13
12 2
1 6
6 11
3 2
13 9
10 9
3 6
9 2
1 5
4 3
1 9
12 13
13 7
1 7
6 2
5 13
8 9
8 5
3 7
8 12
5 7
8 1
13 2
12 4
8 3
1 2
12 5
3 11
7 9
12 9
8 13
6 9
10 11
7 11
1 10
1 11
8 4
5
8 1 12 10 5 4 13 3 6 7 11 9 2 
5 13 8 4 12 7 6 2 3 10 1 11 9 
8 12 1 10 5 4 13 3 6 7 11 9 2 
8 12 1 10 5 4 3 13 6 7 11 9 2 
8 1 12 10 5 4 3 13 7 6 11 9 2 
20 176
10 7
9 8
18 8
6 11
13 18
19 15
1 12
12 18
9 19
4 13
18 20
2 18
6 8
12 5
11 12
7 6
15 17
11 16
8 19
1 6
15 20
6 12
3 1
17 5
1 9
10 6
4 19
13 20
1 8
10 11
3 10
15 16
2 17
11 17
3 6
20 5
11 9
13 1
4 3
7 11
1 19
20 14
18 15
19 5
5 14
1 7
7 17
3 7
3 14
10 5
13 17
13 8
6 19
13 7
2 1
3 8
10 19
7 5
4 1
12 14
18 14
13 6
4 9
16 17
10 15
13 19
1 20
2 13
18 19
2 4
9 14
9 12
4 7
2 3
16 5
6 17
1 17
11 5
3 15
7 16
10 8
7 8
8 20
12 8
11 19
4 8
4 17
1 10
11 14
15 14
12 17
10 20
6 5
4 18
3 9
17 20
4 20
10 14
6 16
18 5
10 9
12 15
12 19
13 3
10 18
6 9
7 12
2 6
10 12
7 15
11 18
9 20
13 15
19 17
9 16
2 7
7 20
2 12
8 14
9 17
10 16
6 14
19 14
3 19
3 12
2 14
1 5
1 16
16 20
9 18
17 14
4 5
19 20
7 9
9 5
3 11
11 20
6 15
8 5
10 17
4 11
13 9
13 10
2 5
1 15
7 14
2 15
3 20
2 11
8 16
4 10
4 15
7 18
6 20
8 17
3 5
1 14
7 19
2 20
12 16
3 18
2 19
12 20
4 14
15 5
3 17
9 15
6 18
1 18
11 8
13 14
13 16
13 11
4 6
11 15
13 12
3
2 4 13 3 1 10 7 6 11 9 12 18 8 19 15 16 17 20 5 14 
2 4 13 3 1 10 7 6 11 9 12 18 8 19 15 16 17 20 5 14 
2 4 13 3 1 10 7 6 11 9 12 18 8 19 15 16 17 20 5 14
Output:
#1 0 1 1 0 0
#2 6 8 0 0 0 12 0
#3 0 0 0 0 0 1 1 0 0 0
#4 0 21 0 0 0
#5 0 0 0