두 경로

정점의 고정 쌍 $(A, B)$와 $(C, D)$가 주어진 방향 비순환 그래프가 있다. $A$에서 $B$로 가는 단순 경로와 $C$에서 $D$로 가는 단순 경로로 이루어진 쌍 중, 두 경로가 간선을 공유하지 않는 모든 경우를 고려한다. 두 경로 길이의 합이 최소인 쌍을 찾는다.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($1 \le n \le 5000$, $0 \le m \le 20\,000$). 다음 $m$개의 줄에는 $u$에서 $v$로 가는 간선이 있음을 뜻하는 정수 $u$와 $v$가 주어진다 ($1 \le u, v \le n$). 이 그래프에는 자기 자신으로 가는 간선, 중복 간선, 사이클이 없다. 마지막 줄에는 고정 정점 $A$, $B$, $C$, $D$가 이 순서대로 주어진다 ($1 \le A, B, C, D \le n$).

두 경로의 쌍이 존재하지 않으면 NO 한 줄만 출력한다. 존재하면 첫 줄에 YES를 출력하고, 이어서 $A$에서 $B$로 가는 경로, $C$에서 $D$로 가는 경로를 차례로 출력한다. 각 경로는 두 줄로 출력한다. 첫 줄에는 경로의 정점 수를, 둘째 줄에는 방문 순서대로 정점 번호를 쓴다. 각 경로는 단순 경로여야 하므로, 같은 경로 안에서 한 정점을 두 번 이상 방문하지 않는다. 답이 여러 개이면 그중 아무거나 출력한다.