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.