A directed graph with input and output (referred as DGIO hereafter) is a graph in which some nodes have dangling edges, such as the one shown in Figure 1, in which the dangling inputs are a, b, c, d, and the dangling outputs are e, f. A DGIO is "sound" if every dangling input is connected with every dangling output through a directed path. The DGIO shown in Figure 1, for example, is unsound, as input c is not connected with output f, and input d is not connected with output e.

Given a DGIO, your first step is to determine whether it is sound. (easy, isn't it? keep reading) If it is unsound, ideally we would like to split it into a minimum number of sound DGIOs. Figures 2 and 3 show two ways to split the unsound DGIO in Figure 1. Figure 3 is a better split than Figure 2 as it splits Figure 1 into fewer DGIOs. Note, that after a split, the edges connecting different DGIOs become new dangling inputs / outputs.

Computing the minimum split of an unsound DGIO sounds tricky, isn't it? You know what, it is NP-hard... We understand that you folks are extremely good at searching and pruning for NP-hard problems, but no matter how skillful you are, an NP-hard problem IS an NP-hard problem, and an exponential algorithm is never going to be scalable and is prohibitively costly on large-scale graphs.

You are, instead, required to compute a "local-optimal" split for an unsound DGIO. A split is local optimal, if no output DGIOs can be

merged to form a sound DGIO.

 As an example, the split in Figure 4 is NOT a local-optimal split of the DGIO in Figure 1, the four DGIOS on the left hand side in Figure 4 can be merged into a sound DGIO, i.e., resulting in Figure 3. On the other hand, both Figures 2 and 3 are local-optimal splits.