`I am trying to solve https://codeforces.com/gym/103470/problem/K.

My solution is similar to the official tutorial(If you don't understand Chineses, it's ok! I write annotation in the code),but I'm troubled with constant factor(maybe not? If my time complexity is not good enough, please point out. qwq ), keeping getting TLE on test 38. :(

I wonder if someone can help me with it, pointing out something wrong with my implementations. qwq

Your code has complexity $$$\Omega(\sum \deg^2)$$$ (which could be $$$\Omega(nm)$$$ worst case) for counting $$$C_3$$$ and $$$C_4$$$.

Why? qwq

I think my code is using the proper way of constructing the new graph and can decrease the time complexity to $$$\mathcal{O}(m\sqrt{m})$$$. qwq

Ahh, I'm sorry. You're probably right. Then you might want to remove the hash table since it's not very efficient.

But without the hash I can't know how many times every edge is contained by $$$C_3$$$, for it requires a way to know the id of an edge with the vertices. qaq

Just store the indices (such as changing the vector to vector<pair<int, int> >) while storing the endpoints owo

That's amazing! Thank you so much for help!!