Link to problem statement (problem D)
For short, in this problem, one is provided the minimal cut matrix T (T(u,v) equals to the minimum cut so that u and v are disconnected), and one needs to find a graph G that satisfies T.
I have solved this problem using the observation: if the solution exists, it must be some sort of spanning trees (it also seems to be the author's solution). However, I have no way to prove my observation. Any hint?