OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges.
How can I show OddPath is NL? I think about it for a long time, the main problem is that I don't know how to get length of the shortest path in non-deterministic log place.
I tried to use coNL = NL to attack this problem. The problem become "find G with the shortest path with even number of edges". Again, I can't deal with "shortest path".