頂点数がNなら、最長経路数はN-1だろ。
簡単にいえば、経路数1からN-1までの全ての経路を列挙して計算してしまう。