Given a undirected graph with $n$ vertices and $m$ edges. Now we assign a direction for each edge and get a directed graph. Prove that, for all possible assignments, the minimum value of the maximum in-degree in the directed graph we get is $\max_{S\subseteq V} \left\lceil \frac{|E(S)|}{|S|}\right\rceil$, where $E(S)$ consists of all edges in $E$ that have both endpoints in $S$.
The hint says that we may can formulate the problem either as a LP, perfect matching or maximum flow problem and consider its duality. But I don't know how to solve this. Thanks!