Tướng quân Thiên Quang đang chuẩn bị đối mặt với một cuộc tấn công quy mô lớn của kẻ thù. Để phòng thủ khu vực, ông đã thiết lập một mạng lưới gồm ~n~ tiền đồn được kết nối bởi ~m~ con đường núi hai chiều, tạo thành một đồ thị xương rồng liên thông: mỗi con đường thuộc về nhiều nhất một chu trình đơn^∗. Mỗi tiền đồn có thể chứa nhiều nhất một người lính. Ban đầu, tiền đồn ~i~ có một người lính đóng quân nếu ~a_i = 1~, và bị trống nếu ~a_i = 0~.

Tin tưởng phó tướng Bá Lộc của mình, Thiên Quang giao cho anh ta việc điều phối trận chiến và yêu cầu anh ta sắp xếp lại quân lính theo một cách bố trí mục tiêu mới ~b~ (trong đó ~b_i = 1~ nghĩa là tiền đồn ~i~ cuối cùng phải có một người lính, ~b_i = 0~ nghĩa là nó phải bị bỏ trống). Dữ liệu đảm bảo rằng ~\sum_{i=1}^n a_i = \sum_{i=1}^n b_i~. Để thực hiện điều đó, anh ta có thể di chuyển các người lính như sau:

• Trong một phút, Bá Lộc có thể chọn một người lính và di chuyển anh ta đến một tiền đồn trống kề cận.

Bá Lộc phải tìm cách đạt được cách bố trí mục tiêu càng nhanh càng tốt. Hãy giúp Bá Lộc tính thời gian tối thiểu để đạt được cách bố trí mục tiêu. Có thể chứng minh rằng luôn có thể đạt được cách bố trí mục tiêu ~b~ từ cách bố trí ~a~ trong các điều kiện đã cho.

∗ Chu trình đơn trong một đồ thị là một dãy các đỉnh ~v_1, v_2, \ldots, v_k~, sao cho:

• đỉnh ~v_i~ và ~v_{i+1}~ (~1 \le i < k~) có cạnh nối,

• đỉnh ~v_1~ và ~v_k~ có cạnh nối,

• ~v_i \ne v_j~ với mọi ~1 \le i < j \le k~.

Input

Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^4~). Mô tả của mỗi test case như sau:

• Dòng đầu chứa hai số nguyên ~n, m~ (~1 \le n \le 2 \cdot 10^5~; ~n - 1 \le m \le \lfloor 3(n-1)/2 \rfloor~) — số cứ điểm và số con đường.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, \ldots, a_n~ (~0 \le a_i \le 1~) — bố trí ban đầu (~a_i = 1~ nghĩa là cứ điểm ~i~ ban đầu có lính).

• Dòng thứ ba chứa ~n~ số nguyên ~b_1, \ldots, b_n~ (~0 \le b_i \le 1~) — bố trí mục tiêu (~b_i = 1~ nghĩa là cứ điểm ~i~ cuối cùng phải có lính).

• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le n~; ~u \ne v~) mô tả một con đường. Không có con đường trùng nhau.

Đảm bảo rằng:

• Mạng lưới tạo thành một xương rồng liên thông,

• ~\sum n \le 5 \cdot 10^5~ trên mọi test case,

• ~\sum_{i=1}^n a_i = \sum_{i=1}^n b_i~.

Output

Với mỗi test case, in ra một số nguyên — số lần hành quân ít nhất để đạt được bố trí mục tiêu ~b~.

Scoring

Sample Input 1

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

Sample Output 1

2
0
6

Sample Input 2

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

Sample Output 2

1
2

Sample Input 3

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

Sample Output 3

1
4

Notes

Trong ví dụ đầu tiên, test 1, người lính ở tiền đồn ~1~ hành quân ~1 \to 2 \to 3~, mất ~2~ phút.

Trong ví dụ thứ hai, test 1, người lính ở tiền đồn ~1~ di chuyển trực tiếp đến tiền đồn trống ~3~ dọc theo con đường ~(3, 1)~, mất ~1~ phút.

Trong ví dụ thứ ba, test 2, hai người lính ở các tiền đồn ~2~ và ~4~ phải lần lượt đi đến các tiền đồn ~5~ và ~1~; mỗi người di chuyển một khoảng cách là ~2~, nên tổng cộng mất ~4~ phút.

————————–

Các test case trong ví dụ đầu tiên đều thỏa mãn subtask 2.

Các test case trong ví dụ thứ hai đều thỏa mãn subtask 3.