Let G be an Eulerian digraph, and let {x(1), x(2)}, {y(1), y(2)} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G; {x(1); x(2)}, {y(1), y(2)}) is called feasible if there is a choice of h, i, j, k with {h, i} = { j, k} = {1, 2} such that G has two arc-disjoint x(h) x(i)- and y(j) y(k)-paths. In this paper, we characterize the structure of minimal infeasible instances, based on which an O(m + n log n) time algorithm is presented to decide whether a given instance is feasible, where n and m are the number of vertices and arcs in the instance, respectively. If the instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m + n log n)) time.