Giải bài trực tuyến

Đất nước X là một đất nước nổi tiếng bởi du lịch với những bãi biển vô cùng đẹp. KrK hiện đang là bộ trưởng bộ giao thông của đất nước, và anh đang đau đầu với những kế hoạch xây dựng cầu đường kết nối các thành phố với nhau. Đất nước X có N thành phố, và có M con đường 2 chiều nối các cặp thành phố. Trong M con đường này, có N-1 con đường là những con đường trọng điểm không thể bị phá hủy. N-1 con đường này kết nối toàn bộ các thành phố, và khi phá hủy bất kỳ con đường nào sẽ dẫn đến việc một vài thành phố không thể đi đến được bởi các thành phố khác. (Chỉ dùng N-1 con đường trọng điểm)

KrK muốn quy hoạch lại hệ thống đường xá của đất nước mình bằng cách xây dựng thêm hoặc phá bỏ đi một vài tuyến đường. Nhưng KrK lại muốn biết rằng sau khi xây dựng và phá bỏ đi tuyến đường đấy, đất nước của anh có bao nhiêu tuyến đường hiểm yếu.

Tuyến đường hiểm yếu là tuyến đường nếu bị phá hủy, đất nước sẽ bị chia cắt làm 2 phần riêng biệt, mà không có con đường nào kết nối 2 phần thành phố này.

Input

Dòng đầu tiên là 2 số nguyên dương N và M – Số lượng thành phố và số lượng con đường của đất nước X.

M dòng tiếp theo chứa 3 số nguyên dương u, v, t (u ≠ v, 1 ≤ u, v ≤ N) mang ý nghĩa có con đường kết nối 2 thành phố u, v, và nếu t = 0 thì con đường này là con đường trọng điểm, t = 1 thì đây là con đường bình thường. Hai thành phố không có quá 1 con đường kết nối chúng.

Dòng tiếp theo chứa số nguyên dương Q – số lượng các cải tổ hệ thống đường xá của KrK (xóa bỏ hoặc xây dựng)

Q dòng tiếp theo chưa 2 số nguyên dương u, v (u ≠ v, 1 ≤ u, v ≤ N). Nếu tồn tại con đường giữa u và v, nghĩa là phá hủy con đường kết nối u, v. Ngược lại nếu chưa tồn tại con đường kết nối u, v nghĩa là xây dựng thêm con đường nối 2 thành phố u và v.

Input luôn thỏa mãn:

• Ban đầu có đúng N-1 con đường loại 0 (Con đường trọng điểm)
• Các con đường trọng điểm không bao giờ bị xóa đi trong các truy vẫn của KrK.

Output

Dòng đầu tiên chưa một số nguyên dương là số lượng tuyến đường hiểm yếu ban đầu của đất nước X.

Q dòng tiếp theo mỗi dòng in ra một số nguyên dương là số lượng tuyến đường hiểm yếu của đất nước X sau mỗi một lần sửa đổi hệ thống giao thông.

Giới hạn

• 1 ≤ N, M ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• Trong 20% số test, N, Q ≤ 1000.

Example

Input:
6 6
1 2 0
1 5 1
1 4 0
5 4 0
6 4 0
2 3 0
4
6 5
1 5
5 6
3 6


Output:
3
2
3
5
1