6.4 Ryn Blackwood’s Adventure: Labyrinth of Lost Voices
Escaping the room, Ryn Blackwood stumbles into the Labyrinth of Lost Voices, a maze of n halls and m one-way passages.
She begins her journey in hall s. Yet the labyrinth’s magic splits her essence into two echoes, each forced to explore different routes.
The echoes must travel from the same starting hall s and meet again at some other hall t.
However, the Labyrinth enforces strict rules:
- Both echoes must start at s and end at the same t.
- Their paths must not share any other halls except s and t.
- Each hall can be visited at most once per path.
- The passages are one-way.
Your task is to determine whether such two distinct paths exist — and reveal them if they do.
Constraints
2 <= n <= 2⋅10^5
0 <= m <= 2⋅10^5
1 <= s <= n
1 <= ui ,vi < =n; ui≠vi
Input Format
The first line contains three integers n, m and s where n is the number of vertices, m is the number of edges in the labyrinth, and s is the starting hall.
Then m lines with descriptions of passages follow. Each description contains two integers ui, vi, denoting a passage from the hall ui to the hall vi. The passages are one-way. The labyrinth can contain cycles and is not necessarily connected in any way.
Output Format
If it is possible to find the desired two paths, output "YES", otherwise output "NO".
If the answer exists, output two path descriptions. Each description occupies two lines. The first line of the description contains an integer x where x denotes the number of halls in the path followed by the second line which contains p1, p2, p3…..px denoting the hall numbers in the path.
Example 1
Input:
5 5 1
1 2
2 3
1 4
4 3
3 5
Output:
YES
3
1 2 3
3
1 4 3
Explanation:
It is possible to have 2 paths starting at 1 with both of them ending at 3.
Log In to solve the Question