Задача №111723. Network Instability
Вася устроился сисадмином в крупную и известную компанию Проблемсофт. В сети компании n компьютеров, некоторые пары которых соединены кабелем напрямую. Всего таких соединений m, причем Вася весьма неплохой администратор, так что никакой кабель не соединяет компьютер с самим собой и каждая пара компьютеров соединена не более чем одним кабелем.
На каждом компьютере в фирме Проблемсофт установлена специальная программа разработанная и поддерживаемая инженерами Проблемсофта, под названием ЗлойЖук. Инженеры этой компании отличаются крайним трудолюбием и высокой производительностью, в связи с чем новые версии программы ЗлойЖук выходят почти ежедневно. Однако, не все сотрудники компании разделяют трудолюбие инженеров, поэтому обновляют программу ЗлойЖук неохотно, и всякий раз до какой-то случайной версии (вполне могут "обновить" до такой же или даже более старой).
После нескольких ужасных месяцев, в течение которых исправлять различные ошибки приходилось днями и ночами, без обедов и выходных, Вася понял в чем причина подавляющего большинства всех сбоев! Причина в том, что компьютеры пересылающие данные по соединяющему их кабелю могут иметь различные версии программы ЗлойЖук. Прямое соединение кабелем двух компьютеров с различными версиями программы ЗлойЖук Вася называет нестабильным.
На последнем корпоративе компании Проблемсофт Вася вместо развлечений ходил с листочком и узнавал у каждого сотрудника когда он планирует обновить программу ЗлойЖук и до какой версии. Нельзя сказать, чтобы коллеги охотно отвечали на эти вопросы, вместо того что купаться в джакузи и пить Кока-Колу, но все-таки Вася смог составить график планируемых изменений версий программы ЗлойЖук на всех компьютерах сети Проблемсофта. Теперь его интересует количество нестабильных соединений в сети после выполнения каждого изменения.
Первая строка входного файла содержит два целых числа n и m (1 ≤ n, m ≤ 105).
Вторая строка содержит n целых чисел v1, v2, ..., vn: версии программы ЗлойЖук изначально установленные на компьютерах Проблемсофта (1 ≤ vi ≤ 105).
Следующие m строк содержат числа ai и bi: описание соединений (1 ≤ ai, bi ≤ n, ai ≠ bi). Гарантируется что сеть хорошая, то есть никакая пара компьютеров не соединена более чем одним кабелем и никакой компьютер не соединен кабелем с самим собой.
Следующая строка содержит целое число q: количество запланированных изменений версий программы ЗлойЖук (1 ≤ q ≤ 105).
Далее следуют q строк; i-ая содержит числа ci и v'i: номер компьютера на котором происходит изменение, и номер новой версии программы ЗлойЖук. Изменения даны в хронологическом порядке, никакия два изменения не происходят одновременно.
Выведите q строк; i-ая строка должна содержать одно целое число: количество нестабильных соединений сразу после выполнения i-го обновления.
4 5 1 2 3 4 1 2 2 3 3 4 4 1 1 3 5 1 5 3 2 4 4 1 4 2 3
5 4 4 3 4