{"problem":{"name":"[USACO22DEC] Making Friends P","description":{"content":"FJ 的 $N(2 \\le N \\le 2 \\times 10^5)$ 头编号为 $1 \\cdots N$ 的奶牛之中初始时有 $M(1 \\le M \\le 2 \\times 10^5)$ 对朋友。奶牛们一头一头地离开农场去度假。第 $i$ 天，第 $i$ 头奶牛离开了农场，同时第 $i$ 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系？ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8907"},"statements":[{"statement_type":"Markdown","content":"FJ 的 $N(2 \\le N \\le 2 \\times 10^5)$ 头编号为 $1 \\cdots N$ 的奶牛之中初始时有 $M(1 \\le M \\le 2 \\times 10^5)$ 对朋友。奶牛们一头一头地离开农场去度假。第 $i$ 天，第 $i$ 头奶牛离开了农场，同时第 $i$ 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系？\n\n## Input\n\n输入的第一行包含 $N$ 和 $M$。\n\n以下 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 是朋友（$1 \\le u_i,v_i \\le N,u_i \\neq v_i$）。每个奶牛无序对至多出现一次。 \n\n## Output\n\n 输出一行，包含形成的新的朋友关系的总数。不要计入初始时已经是朋友的奶牛对。 \n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n第 $1$ 天，三个新的朋友关系被建立：$(3,4)$，$(3,7)$ 和 $(4,7)$。\n\n第 $3$ 天，两个新的朋友关系被建立：$(4,5)$ 和 $(5,7)$。\n\n### 测试点性质\n\n - 测试点 $2-3$ 满足 $N \\le 500$。\n - 测试点 $4-7$ 满足 $N \\le 10^4$。\n - 测试点 $8-17$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8907","tags":["USACO","2022","启发式合并"],"sample_group":[["7 6\n1 3\n1 4\n7 1\n2 3\n2 4\n3 5","5"]],"created_at":"2026-03-03 11:09:25"}}