Cho một đồ thị vô hướng gồm \(N\) đỉnh và \(M\) cạnh. Có 2 loại thao tác:

1. Thêm một cạnh mới vào giữa hai đỉnh \(a\) và \(b\).
2. Xóa một cạnh tồn tại giữa hai đỉnh \(a\) và \(b\).

Tính số thành phần liên thông sau mỗi hành động.

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\): số đỉnh, cạnh và thao tác.
• \(M\) dòng tiếp theo mô tả số đỉnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có một cạnh giữa hai đỉnh \(a\) và \(b\). Có ít nhất một cạnh giữa hai cặp đỉnh bất kì.
• \(K\) dòng tiếp theo mô tả số thao tác. Mỗi dòng gồm ba số nguyên \(t\), \(a\) và \(b\): thêm \((t = 1)\) hoặc xóa \((t = 2)\) một cạnh giữa hai đỉnh \(a\) và \(b\). Cạnh chỉ được tạo khi chưa tồn tại cạnh nào giữa hai đỉnh và chỉ được xóa khi tồn tại một cạnh giữa hai đỉnh.

Constraints

• \(2 \leq N \leq 2\cdot 10^5\)
• \(1 \leq M, K \leq 10^5\)
• \(1 \leq a, b \leq n\)

Output

• In ra \(k + 1\) số nguyên gồm: số thành phần liên thông trước khi thực hiện thao tác và số thành phần liên thông sau mỗi thao tác.

Example

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

2 2 2 1