{"raw_statement":[{"iden":"statement","content":"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.\n\nJarvis 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. \n\nYou 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.\n\nThe first line of the input consists of two integers $n$ and $q$ ($1 <= n, q <= 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 <= x, y <= 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 <= s <= n$), indicating that you must find the number of teams that can participate in a tournament with team size $s$.\n\nFor 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$.\n\n"},{"iden":"input","content":"The first line of the input consists of two integers $n$ and $q$ ($1 <= n, q <= 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 <= x, y <= 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 <= s <= n$), indicating that you must find the number of teams that can participate in a tournament with team size $s$."},{"iden":"output","content":"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$."},{"iden":"examples","content":"Input5 6\n2 2\n1 1 2\n2 2\n2 3\n1 1 3\n2 3\nOutput0\n1\n0\n1\nInput7 9\n2 1\n2 2\n1 1 2\n1 2 3\n1 4 5\n1 5 6\n1 6 7\n2 3\n2 4\nOutput7\n0\n2\n1\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of users.  \nLet $ \\mathcal{G} = \\{G_1, G_2, \\dots, G_m\\} $ be the set of connected components (friend groups) in the undirected friendship graph, where each $ G_i \\subseteq \\{1, 2, \\dots, n\\} $ and $ |G_i| $ is the size of group $ G_i $.  \n\n**Constraints**  \n1. $ 1 \\leq n, q \\leq 10^5 $  \n2. For each query:  \n   - Type 1: $ 1 \\leq x, y \\leq n $, add an edge between users $ x $ and $ y $.  \n   - Type 2: $ 1 \\leq s \\leq n $, compute the maximum number of teams of size $ s $.  \n\n**Objective**  \nFor each query of type 2 with team size $ s $:  \n$$\n\\text{Answer} = \\sum_{G_i \\in \\mathcal{G}} \\left\\lfloor \\frac{|G_i|}{s} \\right\\rfloor\n$$  \nFor each query of type 1:  \nUpdate the connected components $ \\mathcal{G} $ by merging the components containing $ x $ and $ y $.","simple_statement":"You are given n users and q queries. Initially, no one is friends.  \n\nTwo users are in the same friend group if they are directly or indirectly connected by friendships.  \n\nYou must handle two types of queries:  \n- Type 1: x y → Make users x and y friends (merge their friend groups).  \n- Type 2: s → Find how many full teams of size s you can form, where each team must be from one friend group, and each group can send at most one team.  \n\nFor each type 2 query, output the maximum number of teams of size s possible.","has_page_source":false}