{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"4 3\n1 2\n2 3\n1 4"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"3 0"},{"iden":"sample output 2","content":"0\n\nIf there are no initial friendships, no new friendships can occur."},{"iden":"sample input 3","content":"10 8\n1 2\n2 3\n3 4\n4 5\n6 7\n7 8\n8 9\n9 10"},{"iden":"sample output 3","content":"12"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}