Comment by phalf

I could be mixing things up here, it's been too long ago. I think this was about a directed graph, so the number of edges is actually N^2 and your walk roughly of that length.