{"problem":{"name":"New Friends","description":{"content":"There is an SNS used by $N$ users, labeled with numbers from $1$ to $N$. In this SNS, two users can become **friends** with each other.   Friendship is bidirectional; if user X is a friend of user Y, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc350_d"},"statements":[{"statement_type":"Markdown","content":"There is an SNS used by $N$ users, labeled with numbers from $1$ to $N$.\nIn this SNS, two users can become **friends** with each other.  \nFriendship is bidirectional; if user X is a friend of user Y, user Y is always a friend of user X.\nCurrently, there are $M$ pairs of friendships on the SNS, with the $i$\\-th pair consisting of users $A_i$ and $B_i$.\nDetermine the maximum number of times the following operation can be performed:\n\n*   Operation: Choose three users X, Y, and Z such that X and Y are friends, Y and Z are friends, but X and Z are not. Make X and Z friends.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq A_i < B_i \\leq N$\n*   The pairs $(A_i, B_i)$ are distinct.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$\\vdots$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc350_d","tags":[],"sample_group":[["4 3\n1 2\n2 3\n1 4","3\n\nThree new friendships with a friend's friend can occur as follows:\n\n*   User $1$ becomes friends with user $3$, who is a friend of their friend (user $2$)\n*   User $3$ becomes friends with user $4$, who is a friend of their friend (user $1$)\n*   User $2$ becomes friends with user $4$, who is a friend of their friend (user $1$)\n\nThere will not be four or more new friendships."],["3 0","0\n\nIf there are no initial friendships, no new friendships can occur."],["10 8\n1 2\n2 3\n3 4\n4 5\n6 7\n7 8\n8 9\n9 10","12"]],"created_at":"2026-03-03 11:01:13"}}