一個一個數是不能突破 \(O(m \sqrt m)\) 的下界的。
設矩陣乘法的復雜度為 \(O(n^\omega)\)，這里提供一種 \(O(m^{\frac{2\omega}{\omega + 1}})\) 的做法。
例如，使用 Strassen 方法可以將其復雜度降為 \(O(m^{1.475})\)。

算法1. 矩陣乘法

考慮我們枚舉一條邊 \((a, b)\)，接下來需要計數有多少個點 \(c\) 滿足 \((a, c), (b, c)\) 均存在。
設圖的鄰接矩陣為 \(A\)，則由 \((a, b)\) 邊參與形成的三元環個數即為 \(\sum \limits_{i = 1}^{n} A_{a, i} \times A_{i, b}\)
不難看出這是一個矩陣乘法的形式。我們可以求出來 \(B = AA^T\)，然后 \(B_{a, b}\) 即為所求。

這里需要計算一次矩陣乘法，然后 \(O(m)\) 枚舉邊。
由于矩陣乘法不會低于 \(O(n^2)\)，所以復雜度為 \(O(n^\omega)\)。

算法 1 的好處在于，不是一個一個數的，可以突破 \(O(m \sqrt m)\) 的下界。
不過稀疏圖上表現很差就是了。

算法2. 生成樹

這里是另一個算法。
假設圖連通，我們求圖的一個生成樹出來。

然后將三元環拆成以下四種情況：

1. 由三個樹邊組成。顯然不成立。
2. 由一個樹邊兩個非樹邊組成。
3. 由兩個樹邊一個非樹邊組成。
4. 由三個非樹邊組成。

首先看情況 2。
我們枚舉一個點 \(p\)，然后標記所有通過非樹邊與 \(p\) 相連的點。
然后判斷這些點之間由多少祖先關系即可。
這部分的復雜度為 \(O(m)\)。

然后看情況 3。
我們枚舉一條非樹邊 \((a, b)\)，然后判斷 \(a, b\) 兩個點在樹上的距離是否為 \(2\) 即可。
距離為 2 可能是 fa[fa[a]] = b 或者 fa[fa[b]] = a 或者 fa[a] = fa[b]。
這部分復雜度 \(O(m)\)。

最后，將所有非樹邊去掉，然后遞歸處理上述過程即可。

Q：該算法復雜度？
考慮每次刪除一個生成樹，每個點的度至少減一。
所以該過程至多進行 \(n - 1\) 輪。
復雜度即為 \(O(nm)\)。

如果閾值分治并結合暴力該算法也可以分析得到 \(O(m \sqrt m)\) 的復雜度。在此不表。
反正也是一個一個數的，不會低于 \(O(m \sqrt m)\)。
不過在稀疏隨機圖上表現會很好。

閾值分治

上述兩個算法分別在稠密圖和稀疏圖上表現良好。
這里使用閾值分治結合一下。

考慮我們先進行 \(B\) 輪算法 2，然后去掉所有的孤點，對于剩下的點使用算法 1。
所有點的總度數為 \(O(m)\)，進行 \(B\) 輪之后剩下的點在原圖上的度數均 \(>B\)，而這樣的點只有 \(O(\frac{m}{B})\) 個。
所以兩部分的復雜度和為 \(O(mB + \left( \frac{m}{B} \right)^\omega)\)。
取 \(B = m^{\frac{\omega - 1}{\omega + 1}}\) 最優，總復雜度為 \(O(m^{\frac{2\omega}{\omega + 1}})\)。

實現

當然，Strassen 方法常數巨大。
所以我實現矩陣乘的時候直接寫的壓位。復雜度 \(O(\frac{n^3}{w})\)。
總復雜度可以平衡到 \(O(\frac{m \sqrt m}{w^{\frac{1}{4}}})\)。
但是還是跑的很慢。
1.02s

另外，觀察到隨機圖算法 2 遠遠跑不滿。
所以可以嘗試把 \(B\) 縮小并且不改變矩陣大小。
（當然這是能卡的）
這道題給 \(B\) 縮小了 64 倍仍然能過。
266ms

拜謝 UT 提供的復雜度分析指導 orz orz orz