I present a refinement on HEKTO's algorithm that I think works and should be more efficient: it runs in $O^*(\min(n^3,m^2))$ time.
Let $P(a)$ denote the set of paths that start at $s$, go through the arc $a$, and end at $e$.
Lemma 1. $a_1,a_2$ can be given the same color iff $P(a_1)=P(a_2)$.
Let $G^*$ be the dual graph of $G$, i.e., each arc of $G$ is a vertex of $G^*$, and for each pair of arcs $u \to v$, $v \to w$ in $G$ we connect the corresponding vertices with a directed arc in $G^*$. The start vertex of $G^*$ is a new vertex $s_0$, and it has an arc in $G^*$ to each arc $s \to v$ in $G$; and similarly for its end vertex.
Lemma 2. An arc $a_2$ is in every path of $P(a_1)$ iff $a_2$ is a dominator or post-dominator of $a_1$ in $G^*$.
Say that $a_1 \prec a_2$ if $a_1$ is the immediate dominator of $a_2$ and $a_2$ is the immediate post-dominator of $a_1$ in $G^*$.
Lemma 3. $P(a)=P(a')$ iff there exists a sequence of arcs $a_1,\dots,a_n$ such that $a=a_1 \prec a_2 \prec \cdots \prec a_n=a'$.
This theory immediately leads to an efficient algorithm for your problem:
Compute the dominator tree $D$ and post-dominator tree $D'$ of $G^*$.
Initialize a Union-Find data structure with each arc of $G$ in its own set.
For arc $a_1$ of $G$, let $a_2$ be its immediate dominator in $D$; if $a_1$ is the immediate dominator of $a_2$ in $D'$, call Union($a_1,a_2$).
Assign a different color to each set of the Union-Find data structure.
Running time analysis
If $G$ has $n$ vertices and $m$ arcs, then $G^*$ has $m$ vertices and $\min(n^3,m^2)$ arcs. Computing the dominator tree can be done in nearly linear time (see e.g., https://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithms or Dominator Tree for DAG). The Union-Find algorithm can be done in nearly linear time. Thus, the running time is essentially $O(\min(n^3,m^2))$, ignoring logarithmic factors.
I wouldn't be surprised if there is a more efficient way to compute the dominator tree of $G^*$ without constructing $G^*$ explicitly, which would lead to improvements in the running time of this algorithm.
Proof of Lemma 1. If $P(a_1) \ne P(a_2)$, there is some path that goes through $a_1$ but not $a_2$ (or vice versa), and then by the requirements, $a_1,a_2$ cannot be given the same color.
For the converse, suppose we form equivalence classes on the arcs where $a_1,a_2$ are equivalent if $P(a_1)=P(a_2)$, give each equivalence class a unique color, and color each edge according to the color of the equivalence class it is contained in. Then this satisfies all of the constraints: for any color $c$ and any two arcs $a_1,a_2$ colored $c$, we have $P(a_1)=P(a_2)$, so any path $p \in P(a_1)$ also satisfies $p \in P(a_2)$ and thus visits $a_2$; and any path $p \notin P(a_1)$ also satisfies $p \notin P(a_2)$ and thus does not visit $a_2$.
I haven't written out the proofs of Lemmas 2-3, so I recommend you do that and check my reasoning before using this algorithm.