This is effectively creating the bipartite coloring of a graph $G=(V,E)$, if it is bipartite. There can be no bipartite coloring if there are odd length cycles in the graph which you are considering.
You can check to see if a graph is bipartite in $O(|V|\cdot |E|)$, i.e. time proportional to the product of the number of edges and vertices.
If your graph is a single component connected finite graph, start by pick any vertex as a starting point and assign it the distance $0$ (or equivalently the label $(-1)$. Then iterate the following two steps alternately until every vertex is labeled, or until you end up attempting to assign two different labels to the same vertex (i.e. you find two different paths to the same vertex which are not the same length modulo $2$.
pick any vertex as a starting point and assign it the distance $0$ (or equivalently the label $(-1)$. Then iterate the following until every vertex is labeled, or until you end up having attempting to assign two different labels to the same vertex (i.e. you find two different paths to the same vertex which are not the same length modulo $2$.
follow every edge from your vertices labeled $0$ to get the next set of vertices and see if any of them are already labeled $0$, if theythere are then no such bipartition exists. If not, label them with the distance $1$ (oror alternately $(+1)$
follow every edge from the vertices labeled $1$ to get the next set of vertices and see if any of them are already labeled $1$, if theythere are then no such bipartition exists. If not, label them $0$ and continue to iterate.
If you end up attempting to label the same vertex with both labels/colors, then the graph is not bipartite. Otherwise, you end up with every vertex labeled with the parity ($0$=even, $1$=odd) of their distance from the initial vertex chosen for this labeling.