Label-disjoint paths in directed graphs Checking if there are two edge-disjoint paths from $s$ to $t$ 
in a given undirected graph $G$ is in P via a standard solution based on maxflow. 
I am interested in the complexity of the following edge-labeled version and
whether it is in P or not.

Input: An edge-labeled graph $G$ and two vertices $s$ and $t$ satisfying the following condition:


  every label in $G$ occurs exactly twice.  


Output: are there two label-disjoint paths in $G$ from $s$ to $t$?

Two paths are label disjoint iff
the labels appearing in the respective paths are disjoint.

Example: 
suppose $G$ is given by $(s, a, v1)$, $(v1, b, t)$, $(s, b, v2)$, $(s, c, v2)$, $(v2, a, t)$, $(v2, c, t)$. Then $s-a-v1-b-t$ and $s-c-v2-c-t$ are two label-disjoint simple paths from $s$ to $t$.
The problem becomes NP-complete ... this is a "graphical" :-) reduction from 3-SAT ... it should be self-explanatory (... if not let me know).



Two notes:


+X1a, -X1a, +X1b, -X1b,...,+X2a,-X2a, ...,dum1,...,dum4 are all distinct labels;
in the figure  each label appears $\leq 2$ times; but it is straightforward to make each label appears exactly 2 times adding some dum nodes+edges+labels to pair them up.