Why can't u start bfs from each node and when u see distance > 2 u stop bfs?

Here is my solution which actually passed. The idea is you work with edges and use degrees to calculate, then u subtract pairs who are adjacent, that is u counted wrong pairs and you should search for 3 size cycles and subtract all members of that 3 size cycles. About complexity I don't know why it actually passed, the thing is only cycle checking is confusing, probably it can be easily done with dfs (linearly).

Here is my solution which actually passed.

The idea is that you should look at edges and count pairs from both ends.

The only problem we should take care is that we counted pairs who are adjacent, but also 2 edges far away, we should take care of that.

To fix that, we search for all 3 size cycles, and subtract all members of that cycle from the answer and that's it.

Probably 3 size cycle searching can be done in linear time, idk how, I used easy method (can't tell the time complexity of it, probably it is linear as well or closer to linear or test cases are weak), which worked. See code for details.