경기과학고등학교에는 경기과학고등학교만의 자랑스러운 SNS가 있다. 이름하여 경스타그램. 
경스타그램에서 각 학생들은 아이디를 가지고 있으며, 이 아이디는 하나의 정수로 나타낼 수 있다. 
그리고 경스타그램은 서로 모르는 사이더라도 빠르게 친해질 수 있도록 돕기 위해 고유의 기능을 가지고 있는데, 바로 자동 친구 연결 기능이다.
 이 기능은 다음과 같이 작동한다.


 또한, 경스타그램은 친구 그룹을 생성할 수 있다. 
친구 그룹은 몇 명의 학생으로 이루어진 집합으로, 친구 그룹에 속한 서로 다른 두 친구 사이에는 친구 연결이 있어야 한다. 
경스타그램의 관리자인 정후는 경기과학고등학교 입학 예정인 41기 학생들에게 경스타그램 초대장을 보냈다. 
이윽고 N명의 41기 학생들이 경스타그램에 회원 가입했다. 그리고 정후는 생성할 수 있는 친구 그룹의 크기의 최댓값에 관심이 있다. 
그래서 정후는 경스타그램에 ‘미션’ 기능을 추가해, 친구 그룹의 크기의 최댓값을 알려 주는 사람에게 대가를 지불하기로 했다. 
경스타그램은 입소문을 타고 빠르게 퍼져, 많은 수의 가입 요청이 발생하기 시작했다. 
이와 동시에, 경스타그램을 마음에 들지 않아하는 학생들도 생겨났고, 탈퇴 요청 역시 발생하기 시작했다. 

각 Q개의 요청은 다음과 같이 나타난다.
· 1 p : 아이디가 p 인 학생이 경스타그램에 가입한다. 
· 2 p : 아이디가 p 인 학생이 경스타그램에서 탈퇴한다. 

정후에게로부터 대가를 바라는 당신은 정후를 도와 초기와 각 요청 이후에 친구 그룹의 크기의 최댓값을 매번 정후에게 알려 주기로 했다. 

제한

· 1 ≤ N, Q ≤ 200,000
· 각 학생의 아이디는 1 이상 10⁹ 이하의 정수이다. 
· 서로 다른 두 학생의 아이디는 서로 다르다. 
· 탈퇴한 학생이 다시 가입할 수도 있다. 
· 한 학생은 경스타그램에 동시에 한 번만 가입한다. 
· 경스타그램에 가입하고 탈퇴하는 모든 학생은 경기과학고등학교 41기이다. 다시 말해, 자동 친구 연결 기능 외의 방법으로 만들어지는 친구 연결이 없다. 
· 경스타그램의 회원 수는 항상 적어도 한 명이다. 
· 한 명짜리 친구 그룹은 언제나 생성할 수 있다. 
· 각 요청은 항상 유효하다. 다시 말해, 가입 요청하는 아이디는 경스타그램에 없는 상태이며, 탈퇴 요청하는 아이디는 경스타그램에 있는 상태이다. 
· 주어지는 모든 수는 정수이다.

첫째 줄에 두 정수 N과 Q가 공백으로 구분되어 주어진다. 
둘째 줄에 초기 가입 아이디를 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 
셋째 줄부터 Q+2째 줄까지 Q개의 줄에 걸쳐, i 째 줄에 각 요청을 나타내는 두 정수 t_i , p_i 가 주어진다. 
t_i = 1 이면 i 째 요청이 아이디가 p_i 인 학생의 가입 요청이며, t_i = 2 이면 i 째 요청이 아이디가 p_i 인 학생의 탈퇴 요청이다.

초기와 각 쿼리 이후 친구 그룹의 크기의 최댓값을 나타내는 정수를 한 줄에 하나씩, Q+1개의 줄에 걸쳐 출력한다.

2022algorithm