산책과 쿼리

성서는 숭실대학교 근처 자취 후보 장소를 $N$개 선정해 $1$부터 $N$까지 번호를 붙였다. 각 장소에는 자취방이 정확히 하나씩 있다. 자취방을 고를 때 고려할 사항은 여러 가지지만, 성서는 그중에서도 산책의 자유도를 가장 중요하게 본다.

산책로 $(a,b)$는 서로 다른 두 장소 $a$와 $b$를 잇는 길이다. $a$에서 $b$로 걷는 데 $1$의 시간이 걸리고, $b$에서 $a$로 걷는 데도 $1$의 시간이 걸린다. 한 번 걷기 시작하면 중간에 방향을 바꾸거나 멈출 수 없고, 정확히 $1$의 시간 동안 걸어서 반대편에 도착해야 한다.

산책은 어떤 장소 $u$에서 출발해 산책로를 따라 걷다가 마지막에 다시 $u$로 돌아오는 행동이다. 산책 도중에 같은 장소나 산책로를 여러 번 지나도 되지만, 잠시라도 걸음을 멈추면 안 된다.

성서는 장소들 사이를 둘러보며 분위기가 좋은 산책로를 자신만의 산책로 리스트에 추가하려고 한다. 만족스러운 산책은 산책로 리스트에 적힌 산책로만 사용하는 산책이다.

성서는 충분히 긴 시간 산책하다가 원하는 시간에 맞춰 돌아오고 싶어 한다. 자취방 $u$가 산책의 자유도가 높다는 것은, $10^6$ 이상의 어떤 정수 $t$를 고르더라도, 장소 $u$에서 출발해 정확히 $t$의 시간이 걸리는 만족스러운 산책이 존재한다는 뜻이다.

처음에는 산책로 리스트가 비어 있다. 성서는 분위기 좋은 산책로를 발견할 때마다 리스트에 추가한다. 리스트가 바뀔 때마다 산책의 자유도가 높은 자취방이 몇 개인지 구해 보자.

구체적으로 다음 쿼리를 $Q$번 처리해야 한다.

• a b: 산책로 $(a,b)$를 산책로 리스트에 추가한다. 이후 산책의 자유도가 높은 자취방의 개수를 출력한다.

예를 들어 자취방이 $6$개이고 산책로 리스트가 $\{(1,2), (2,3), (1,3), (4,5)\}$라면 위 그림처럼 표현할 수 있다.

자취방 $6$에서는 $10^6$의 시간이 걸리는 만족스러운 산책을 할 수 없으므로 산책의 자유도가 높지 않다.

자취방 $4$와 $5$에서는 $10^6$이나 $10^6+2$ 등의 시간이 걸리는 만족스러운 산책은 할 수 있지만, $10^6+1$이나 $10^6+3$ 등의 시간이 걸리는 만족스러운 산책은 할 수 없으므로 산책의 자유도가 높지 않다.

반면에 자취방 $1,2,3$은 $10^6$, $10^6+1$, $10^6+2$, $10^6+3$, $\cdots$의 시간이 걸리는 만족스러운 산책이 모두 가능하므로 산책의 자유도가 높다.

따라서 위 그림에서 산책의 자유도가 높은 자취방의 개수는 $3$이다.

첫째 줄에 장소의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄부터 $Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 쿼리에서 추가되는 산책로가 연결하는 두 장소 $a_i$, $b_i$가 공백으로 구분되어 주어진다.

쿼리가 주어질 때마다 한 줄에 하나씩 정답을 출력한다.

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 6 \times 10^5$
• $1 \leq a_i < b_i \leq N$ $(1 \leq i \leq Q)$
• 같은 쿼리가 여러 번 주어지지 않는다.
• 주어지는 수는 모두 정수이다.

입출력 양이 많으므로 문제지 2에서 4쪽의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.