Конрад — консультант по человеческим отношениям, работающий в VoltModder, крупном производителе электрооборудования. Сегодня ему было поручено оценить уровень счастья в компании.
В VoltModder работает $$$n$$$ человек, пронумерованных от $$$1$$$ до $$$n$$$. Каждый работник зарабатывает разное число денег — изначально, $$$i$$$-й человек зарабатывает $$$i$$$ рублей в день.
В каждый из $$$q$$$ следующих дней, зарплаты будут пересмотрены. В конце $$$i$$$-го дня работник $$$v_i$$$ начнет получать $$$n+i$$$ рублей в день и станет самым оплачиваемым работником в компании. Его зарплата будет оставаться такой же до её следующего пересмотра.
Некоторые пары людей не любят друг друга. Это создает в компании большое психологическое напряжение. Формально, если два человека $$$a$$$ и $$$b$$$ не любят друга друга, и $$$a$$$ зарабатывает больше денег, чем $$$b$$$, работник $$$a$$$ похвастается этим $$$b$$$. Опасная тройка это тройка из трех таких работников $$$a$$$, $$$b$$$ и $$$c$$$, что $$$a$$$ похвастается $$$b$$$, который, в свою очередь, похвастается $$$c$$$. Если $$$a$$$ не любит $$$b$$$, то и $$$b$$$ не любит $$$a$$$.
В начале каждого дня, Конрад должен посчитать количество опасных троек в компании. Можете ли вы ему помочь в этом?
В первой строке записаны два целых числа $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — количество работников в компании и количество пар работников, которые не любят друг друга. Каждая из следующих $$$m$$$ строк содержит по два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$) описывающих, что работники $$$a_i$$$ и $$$b_i$$$ ненавидят друг друга (то есть $$$a_i$$$ не любит $$$b_i$$$ и $$$b_i$$$ не любит $$$a_i$$$). Каждое такое взаимоотношение будет упомянуто ровно один раз.
В следующей строке записано целое число $$$q$$$ ($$$0 \le q \le 100\,000$$$) — количество пересмотров зарплаты. $$$i$$$-я из следующих $$$q$$$ строк содержит одно целое число $$$v_i$$$ ($$$1 \le v_i \le n$$$), описывающее, что в конце $$$i$$$-го дня, работник $$$v_i$$$ будет получать больше всего денег.
Выведите $$$q + 1$$$ целое число. $$$i$$$-е из них должно содержать количество опасных троек в компании в начале $$$i$$$-го дня.
4 5 1 2 2 4 1 3 3 4 2 3 2 2 3
4 3 2
3 3 1 2 2 3 1 3 5 1 2 2 1 3
1 1 1 1 1 1
Рассмотрим первый пример. $$$i$$$-я строка в следующей иллюстрации показывает структуру компании в $$$i$$$-й день. Ориентированное ребро из $$$a$$$ в $$$b$$$ описывает, что работник $$$a$$$ похвастается работнику $$$b$$$. Опасные тройки показаны подсвеченными ребрами.
