Assume directed graph G (V, E). Assume s, t are the two nodes of graph G. Also assume that it is given in adjacency list representation.

Usually to find a path from s to t, we use a BFS to determine whether t will be an encountered node in a search from s onwards.

Now let u and v be separate nodes in G but not s or t. Give an algorithm for the following:

1) Determine whether G has a path existing from s to t and avoids using both the nodes u and v?

2) Determine whether G has a path existing from s to t and uses both the nodes u and v?

Algorithms must run in O(m+n) time. No pseudocode is required, simply the declaration of the logic of usage of BFS (if required) from node x to node y is enough.