[USACO22DEC] Making Friends P

Luogu
IDLGP8907
Time3000ms
Memory256MB
DifficultyP5
USACO2022启发式合并
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$ 头奶牛的所有仍在农场的朋友互相都成为了朋友。问总共建立了多少新的朋友关系? ## Input 输入的第一行包含 $N$ 和 $M$。 以下 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$,表示奶牛 $u_i$ 和 $v_i$ 是朋友($1 \le u_i,v_i \le N,u_i \neq v_i$)。每个奶牛无序对至多出现一次。 ## Output 输出一行,包含形成的新的朋友关系的总数。不要计入初始时已经是朋友的奶牛对。 [samples] ## Note ### 样例 1 解释 第 $1$ 天,三个新的朋友关系被建立:$(3,4)$,$(3,7)$ 和 $(4,7)$。 第 $3$ 天,两个新的朋友关系被建立:$(4,5)$ 和 $(5,7)$。 ### 测试点性质 - 测试点 $2-3$ 满足 $N \le 500$。 - 测试点 $4-7$ 满足 $N \le 10^4$。 - 测试点 $8-17$ 没有额外限制。
Samples
Input #1
7 6
1 3
1 4
7 1
2 3
2 4
3 5
Output #1
5
API Response (JSON)
{
  "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输入的第一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments