Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs
I'll provide a naive approach which give $O(m^2 \cdot max_f)$ running time but shows the problem is P. First turn the graph to undirected graph. Suppose one edge is in first graph and the other in the second graph, contract both of them and name them $s,t$. We can find a minimum edge cut that separates s and t in time max_f which is a running time of best maximum flow algorithm on unit weight graph. We run this algorithm for all possible pair of edges. But why this works? trivially there is no smaller cut and the two sides are not edgeless. On the other hand if a graph G is connected  minimum edge cut C between two vertices s, t always cuts the graph into two connected subgraphs.