This is effectively creating the bipartite coloring of a graph, 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 time proportional to the product of the number of edges and vertices.
If your graph is a single component connected finite graph,
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 they are then no such bipartition exists. If not, label them $1$ (or 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 they 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.