Thanks to authors

And what's cool here? IMHO, quite standard DP. Don't understand, why so few authors have solved it...

It was cool in finding proper layout (for me at least). Of course, counting routes was trivial.

Problem is very difficult.
I think that answer is maximal cycles degree of vertices,
or maxilal number of cycles containing some vertex.

All Right but max lengs of  cycles must be used also.
Test:
14 91
1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14
2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14
3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14
4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4  14
5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14
6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14
7 8 7 9 7 10 7 11 7 12 7 13 7 14
8 9 8 10 8 11 8 12 8 13 8 14
9 10 9 11 9 12 9 13 9 14
10 11 10 12 10 13 10 14
11 12 11 13 11 14
12 13 12 14
13 14

Answ: 8463398736

Indeed, very cool problem when trying to prove it.