Mạng lưới của Syrjälä có \(n\) máy tính và \(m\) kết nối giữa chúng. Mạng lưới gồm các thành phần các máy tính có thể gửi tin nhắn cho nhau.

Không ai ở Syrjälä biết cách mạng lưới hoạt động. Vì lý do này, nếu một kết nối gặp sự cố, sẽ không ai sửa nó. Trong tình huống này, một thành phần có thể bị chia thành hai thành phần.

Nhiệm vụ của bạn là tính số lượng thành phần sau mỗi sự cố kết nối.

Input

Dòng đầu tiên là ba số nguyên \(n, m\) và \(k\) : số lượng máy tính, kết nối và sự cố. Các máy tính được đánh số \(1,2,...,n\).

Tiếp theo là \(m\) dòng mô tả các kết nối. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : có một kết nối giữa hai máy \(a\) và \(b\). Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy.

Cuối cùng là \(k\) dòng mô tả các sự cố. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : kết nối giữa hai máy \(a\) và \(b\) gặp sự cố.

Output

Sau mỗi sự cố, in ra số lượng thành phần.

Giới hạn

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \cdot 10^5\)
• \(1 \le k \le m\)
• \(1 \le a,b \le n\)

Ví dụ

Input

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

Output

2 2 3