Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Có ~2~ loại thao tác cần thực hiện:

• ~1.~ Thêm ~1~ cạnh giữa ~2~ đỉnh ~a~ và ~b~.

• ~2.~ Xóa ~1~ cạnh giữa ~2~ đỉnh ~a~ và ~b~. Dữ liệu đảm bảo tồn tại cạnh giữa đỉnh ~a~ và ~b~ trước khi xóa.

Nhiệm vụ của bạn là đếm số thành phần liên thông của đồ thị sau mỗi thao tác được thực hiện

Input

Dòng đầu tiên gồm ~3~ số nguyên ~n, m, k~ (~2 \le n \le 10^5, 1 \le m, k \le 10^5~)

~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số ~a, b~ là ~1~ cạnh của đồ thị ban đầu. Có tối đa ~1~ cạnh giữa ~2~ đỉnh bất kì. (~1 \le a, b \le n~)

~k~ dòng tiếp theo, mỗi dòng gồm ~3~ số ~t, a, b~. Khi ~t = 1~ (thêm cạnh) hoặc ~t = 2~ (xóa cạnh). ~1~ cạnh được thêm giữa ~2~ đỉnh khi chưa tồn tại cạnh giữa ~2~ đỉnh đó, và chỉ cạnh đã tồn tại có thể được xóa.

Output

In ra ~k + 1~ số: đầu tiên là số thành phần liên thông trước khi các thao tác diễn ra, và số thành phần liên thông sau mỗi thao tác biến đổi.

Sample Input 1

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

Sample Output 1

2 2 2 1