Two Paths

You are given a directed acyclic graph with two fixed pairs of vertices: $(A, B)$ and $(C, D)$. Consider all pairs of edge-disjoint simple paths, one from $A$ to $B$ and another from $C$ to $D$. Find the pair with minimal total length.

The first line contains two integers $n$ and $m$: the number of vertices and edges in the graph ($1 \le n \le 5000$, $0 \le m \le 20\,000$). Each of the next $m$ lines contains two integers $u$ and $v$, meaning there is an edge from $u$ to $v$ ($1 \le u, v \le n$). The graph has no loops, no multiple edges, and no cycles. The last line contains the fixed vertices in the order $A$, $B$, $C$, $D$ ($1 \le A, B, C, D \le n$).

If no pair of paths exists, print a single line with the word NO. Otherwise, print YES on the first line, then the path from $A$ to $B$, then the path from $C$ to $D$. Each path takes two lines: the number of vertices in the path, then the vertices in the order they are visited. Each path must be simple, so no vertex appears more than once in the same path. If several solutions exist, print any of them.