Problem Link

EGGFREE

Description

Let's call a directed graph egg-free if it is acyclic and for any three pairwise distinct vertices x, y and z, if the graph contains edges x→y and x→z, then it also contains an edge y→z and/or an edge z→y.

You are given an undirected graph with N vertices (numbered 1 through N) and M edges (numbered 1 through M). Find a way to assign a direction to each of its edges such that the resulting directed graph is egg-free, or determine that it is impossible. If there are multiple solutions, you may find any one.