Complexity of acyclicity of a "nondeterministic" graph
The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category.
The algorithm they suggest is quite simple (in hindsight): look for a vertex $v_0$ which is never the target of any edge, and if you find one, force every candidate edge that could begin at the vertex $v_0$ to begin there. If no such $v_0$ exists, then there is no solution.