29171번 - Книжная коллекция Губки Боба 다국어

문제

Недавно Губка Боб купил себе коллекцию из 2ドル n$ книг по истории дна. Коллекция устроена следующим образом: каждая книга имеет свой уникальный порядковый номер, первые $n$ номеров коллекции содержат в себе раннюю историю дна, а следующие $n$ книг с номерами от $n+1$ до 2ドル n$ повествуют новую историю. Для коллекции Боб выделил целую полку и поставил книги в порядке возрастания их порядковых номеров.

Губка Боб ушел на работу, а дома остался его любимый питомец улитка Гэрри. Гэрри очень шаловливый для своего вида, поэтому начал сразу же переставлять книги. Переставляя книги, он вынимает ровно две из них, затем ставит первую на старую позицию второй, а вторую на старую позицию первой. Таким образом, он просто меняет книги местами.

Вернувшись домой, Губка Боб обнаружил шалость Гэрри и был сильно недоволен. К счастью, в комнате стояла камера, которая зафиксировала каждое действие Гэрри. И теперь Губка Боб очень любит коллекцию книг по ранней истории дна, и теперь по данным камеры он хочет узнать, сколько книг с номерами от 1 до $n$ было среди первых $n$ книг на полке после каждого переставления Гэрри. Более формально, после каждой смены книг местами Губка Боб хочет знать количество чисел $x,ドル таких, что 1ドル \le x \le n$ и книга с номером $x$ находится среди первых $n$ на полке.

Губка Боб готов предоставить вам записи перестановок книг, а также просит вас написать программу, которая после каждой перестановки будет вычислять количество книг по ранней истории дна, которые находятся на полке в позициях от 1 до $n$.

입력

В первой строке входного файла содержится одно целое число $n$ (1ドル \le n \le 100,000円$) --- количество книг по старой истории дна, равное количеству книг по новой истории дна.

Во второй строке входного файла дано число $m$ (1ドル \le m \le 100,000円$) --- количество перестановок, которые совершил Гэрри.

В следующих $m$ строках записаны пара чисел $i_k,ドル $j_k$ (1ドル \le i_k, j_k \le 2 n$), которые означают, что $k$-ой перестановкой Гэрри поменял местами книги, которые стояли в позициях $i_k,ドル $j_k$.

출력

В единственной строке выходного файла выведите $m$ чисел --- количество книг по старой истории дна, которые находятся на полке в позициях от 1 до $n,ドル после каждой перестановки Гэрри.

제한

힌트