This answer is an improvement for my (already accepted) original answer, which describes an exact, but potentially very slow algorithm. This improvement was inspired by the @pcpthm answer, however I don't employ any randomization here, so this algorithm also produces the exact coloring.
For each arc $a \in A$ let's consider a set of arcs $R(a) \subset A$, reachable from the arc $a$ in both forward and backward directions. Any arc $a \in A$ is reachable from itself, so $a \in R(a)$. We can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if $R(a_1) = R(a_2)$. So, as in my original answer, we can define an equivalence relation on the set $A$:
$$(a_1 \sim a_2) \equiv (R(a_1) = R(a_2))$$
A minimum number of colors, needed to color all the arcs in the graph $G$ according to your restriction, will be equal to the number of equivalence classes for the relation above.
We can compute sets $R(a)$ for each arc $a \in A$, using the iterative process, similar to one, described in the @pcpthm answer. 945
For each vertex $u \in V$ we define two sets of arcs - a set $F(u) \subset A$ of arcs, forward-reachable from the vertex $u$, and a set $B(u) \subset A$ of arcs, backward-reachable from the vertex $u$. For any arc $a=(u,v)$ we can represent its $R(a)$ as a union of three non-intersecting sets:
$$R(a) = B(u) \cup {(u,v)} \cup F(v)$$
Sets $F(u)$ and $B(u)$ for each vertex $u \in V$ can be computed using topological ordering on the set $V$. For example, the backward (according to this ordering) scan of the set $V$ will give us all the sets $F(u)$ using the formula:
$$F(u) = \bigcup_{v \in N_{out}(u)}({(u,v)} \cup F(v))$$
where $N_{out}(u)$ - open "out"-neighborhood of the vertex $u$. Each such set can be represented by a binary number of the length $m=|A|$. The union operation here for large $m$ can be performed in $O(m)$ time, so the total time to compute all the $R(a)$ will be $O((n+m)m)$.
This algorithm is slower than the randomized algorithm in the @pcpthm answer, however it looks like it's the price we need to pay for the exact solution. The culprit is a necessity to work with large sets of arcs, which can't be represented by a single machine word. 743