解题思路
我们需要从给定的 m 对好友关系中选出两对，使得这两对涉及的 4 名用户互不相同。直接枚举两对关系的组合时间复杂度为 O(m2)，无法承受。考虑互补的角度：所有可能的选两对好友关系的方案总数为 (2m)，减去其中存在“重叠用户”的方案数，即可得到满足条件的方案数。
所谓“重叠用户”，是指所选的两对好友关系中包含相同的用户。由于好友关系均为无向边且无自环、无重边，一条关系对应两个不同用户。若两对关系有公共用户，则只能是共享某个用户 i，而与该用户相连的好友关系至少有两条。对于用户 i，设其度数为 di（即与其直接相连的好友关系数量），则从这 di 条关系中任选两条，都会导致这两对关系共享用户 i，不满足“4 名用户全部互不相同”。根据容斥原理，恰好共享一个公共点的方案数为每个用户 i 贡献的 (2di) 之和，且不同用户贡献的方案互不重叠（因为一个用户无法同时成为两个不同用户的共享点而导致重复计数，题干保证无重边，选出的两对关系若共享两点就会退化成同一条边被选两次，但这种情况在组合数中不会被计算，因为是从 m 条不同边中选两条）。因此，有效方案数为：
Answer=(2m)−i=1∑n(2di)
