If there is a directed cycle in the graph, then the answer is obviously NO.Otherwise answer is always YES. A construction can be made by induction. You keep on adding edges one by one, directing them arbitrarily, such that you don't form any cycle. suppose after adding k edges there is no cycle, but now both the directions that you direct the (k + 1)th edge will form a cycle, in this case you can remove the (k + 1) edge and these two cycles combined will form a bigger cycle. but that's contraditiction to our assumption that there were no cycle until k edges.