In a directed graph, a pair of nodes $$$(a,b)$$$ is good if we have at least:

1) One path $$$x$$$ starting at a node with indegree 0 and ending at $$$a$$$.

2) And one path $$$y$$$ starting at a node with indegree 0 and ending at $$$b$$$.

Where $$$x$$$ and $$$y$$$ don't share any node. It turns out that $$$(a,b)$$$ is not good only if:

1) At least $$$a$$$ or $$$b$$$ is/are not reachable from a node with indegree 0.

2) Or all paths which start at node with indegree 0 and end at $$$a$$$ or $$$b$$$ share at least one common node.

What is the proof of the $$$2^{nd}$$$ point?

Note: The graph can be cyclic, but no self loops or parallel edges.

Hint: rewrite the problem as an instance of maxflow and consider the minimum cut.

So, if we guarantee that both node $$$a$$$ and $$$b$$$ are reachable for node/s with in-degree $$$0$$$, and:

1) Added a source node $$$S$$$ with out-going edges to all nodes with in-degree $$$0$$$.

2) Added a sink node $$$T$$$ with in-going edges from $$$a$$$ and $$$b$$$.

3) Split every node $$$i$$$ (except $$$S$$$ and $$$T$$$) to $$$2$$$ nodes $$$i_1$$$ and $$$i_2$$$, with an edge from $$$i_1$$$ to $$$i_2$$$ (to guarantee that all used paths don't share any nodes).

4) Set the capacities of all edges to $$$1$$$.

Then ran max flow, it will be $$$1$$$ if $$$(a,b)$$$ is not good, which means min cut is $$$1$$$ too. So, the minimum number of edges which if are removed the graph will be disconnected is $$$1$$$. The min cut edge can be:

1) From $$$S$$$ to node $$$i$$$ (which means any path will have $$$i$$$).

2) Or from node $$$i_2$$$ to node $$$j_1$$$ (which means any path will have the edge $$$(i,j)$$$, which implies having nodes $$$i$$$ and $$$j$$$).

3) Or from node $$$i_1$$$ to node $$$i_2$$$ (which means any path will have node $$$i$$$).

Thanks a lot for the useful hint.