Розглянемо неорієнтований граф, який складається з \(n\) вершин і \(m\) ребер. Є два типи подій, які можуть статися:

• між вершинами \(a\) і \(b\) створюється нове ребро.
• Існуюче ребро між вершинами \(a\) і \(b\) видаляється.

Ваше завдання - повідомляти кількість компонентів після кожної події.

Обмеження

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

Формат вхідних даних

У першому рядку вхідних даних є три цілі числа \(n\), \(m\) і \(k\): кількість вершин, ребер і подій.

Після цього є \(m\) рядків, що описують ребра. Кожен рядок має два цілих числа \(a\) і \(b\): між вершинами \(a\) і \(b\) є ребро. Між будь-якою парою вершин є щонайбільше одне ребро.

Потім іде \(k\) рядків, що описують події. Кожен рядок має вигляд "\(t\) \(a\) \(b\)", де \(t\) дорівнює 1 (створити нове ребро) або 2 (видалити ребро). Нове ребро завжди створюється між двома вершинами, між якими ще немає ребра, і можна видалити лише існуючі ребра.

Формат вихідних даних

Вивести \(k+1\) цілих чисел: спочатку кількість компонентів до першої події, а потім нову кількість компонентів після кожної події.

Приклад вхідних даних

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

Приклад вихідних даних

2 2 2 1