Problem on strongly connected directed graph involving $\gcd$ Let $G=(V,E)$ be a strongly connected directed graph. Suppose that $p$ is the greatest common divisor of the lengths of cycle in $G$. How one can prove that there exists a partition $V_0,...,V_{p-1}$ of $V$ such that for every $(v_1,v_2)\in E$ there is $ 0\leq i\leq p-1$ with $v_1\in V_i$ and $v_2\in V_{i+1}$, where $V_0=V_p$
Thank you!
 A: A strong connected digraph in which all cycles have length $0$ modulo $p$ is called $p$-periodic. If $p=1$ then it is also called aperiodic. The statement is trivially true when $p=1$ so let us suppose $p\ge 2$.
We will induce a relation on the vertices of $G$. Fix some vertex $v_0$ and consider distances from $v_0$ modulo $p$. We will write $v_i \sim v_j$ if the distance from $v_0$ to $v_i$ and $v_j$ are the same modulo $p$.
Theorem: The relation $\sim$ defined above is well-defined and is an equivalence relation.
Proof: First, we prove that the notion of "distance from $v_0$" is well-defined. To do this, we show that every path from $v_0$ to $v_i$ has the same distance modulo $p$. 
First, fix an arbitrary path $P$ from $v_i$ to $v_0$. Suppose that $P$ has length $k$ modulo $p$. Then consider any path $Q$ from $v_0$ to $v_i$. It follows that $PQ$ is a cycle through $v_0$ and $v_i$. By assumption, this cycle has length $0$ modulo $p$ and hence $Q$ must have length $p-k$ modulo $p$. Since $Q$ was arbitrary, the statement follows.
Also, it is clear that $~$ is an equivalence class since the relation partitions the vertex set into exactly $p$ equivalence classes: the distances modulo $p$ from $v_0$. $\square$
Let $V_i$ denote the equivalence class with distance $i$ modulo $p$ from $v_0$. Then $V_i$ forms the desired partition of $G$. Indeed, if $(v_1,\ v_2)$ is an edge and $v_1 \in V_i$ then it follows that $V_{i+1}$.
