407282: GYM102741 J E-Sports Tournament

Jarvis is developing a new gaming platform where users can purchase games and play online together called Vapor. On Vapor, users can become friends with other users to increase the size of their friend groups. Two users are in the same friend group if and only if they are friends or one user is friends with someone in the same friend group as the other user.

Jarvis wants to add new functionality to Vapor to help organize e-sports tournaments with teams of fixed size to attract more users to the site, but he isn't sure how big he can make the tournaments. A team is valid if and only if all of the users in the team belong to the same friend group because users refuse to play with people they aren't acquainted with. Furthermore, each friend group will only send one team at maximum to each tournament to avoid infighting within the group.

You need to program a system that given the current state of the Vapor friend network will be able to find out how many valid teams can participate in a tournament with a given team size. You will need to process two types of queries. For query type $$$1$$$, you will be given two integers $$$x$$$ and $$$y$$$, which indicates that users $$$x$$$ and $$$y$$$ are now friends. For query type $$$2$$$, you will be given an integer $$$s$$$, and you must output the maximum number of valid teams of size $$$s$$$ that can compete in the tournament. Initially, all users do not have any friends.

The first line of the input consists of two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 10^5$$$) — the number of Vapor users and the number of queries to process. The next $$$q$$$ lines of the input are one of two query types. If the line begins with a $$$1$$$, there will be two more integers on the line $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$) indicating that $$$x$$$ and $$$y$$$ are now friends. If the line begins with a $$$2$$$, there will be one more integer on the line $$$s$$$ ($$$1 \leq s \leq n$$$), indicating that you must find the number of teams that can participate in a tournament with team size $$$s$$$.

For each query of type $$$2$$$, output a single integer and new line representing the maximum number of valid teams that can participate in a tournament with team size $$$s$$$.

5 6
2 2
1 1 2
2 2
2 3
1 1 3
2 3

0
1
0
1

7 9
2 1
2 2
1 1 2
1 2 3
1 4 5
1 5 6
1 6 7
2 3
2 4

7
0
2
1