9078: Journey

Alice is a young girl who enjoys adventure and solving puzzles. One day, she finds herself in a mysterious and ancient forest, where a magical maze called the "Colorful Maze" is hidden.

The Colorful Maze is an undirected connected graph consisting of $n$ rooms and $m$ corridors. Each room is colored either red or blue, and the corridors form various connections between the rooms.

Initially, Alice is teleported to the starting point of the maze, which is room number $1$. Her goal is to find a path that leads to the endpoint of the maze, which is room number $n$.

However, the maze's magical rules perplex Alice. Whenever she moves from one room to another through a corridor, the color of the destination room changes to the opposite color of the original color. For example, if the room was originally red, it will turn blue after Alice moves to it.

The challenge is for Alice to find a path starting from the starting point, passing through a series of rooms, and finally reaching the endpoint while ensuring that all rooms have either all red or all blue colors.

Alice seeks your assistance in solving this problem and finding a path that meets the requirements. She wants to know if such a path exists. If there is a solution, she would like you to provide a path that consists of no more than 5×1055 \times 10^55×105 corridors.

Now, please help Alice solve this puzzle and provide a valid path if it exists. If it is not possible to find such a path, please inform Alice that it is currently impossible to reach the endpoint. May you aid Alice successfully navigate through the adventure in the Colorful Maze!

The first line of input contains two positive integers $n$ and m(1<n≤105,1≤m≤106)m(1 < n \leq 10^5, 1 \leq m \leq 10^6)m(1<n≤105,1≤m≤106), representing the number of rooms and corridors in the undirected graph.
The next line contains $n$ integers colori(0≤colori≤1)color_i(0\leq color_i \leq 1)colori(0≤colori≤1), representing the colors of each room, $0$ indicates blue, and $1$ indicates red.
The next $m$ lines each contain two integers $u$ and v(1≤u,v≤n)v(1 \leq u,v \leq n)v(1≤u,v≤n), representing an undirected corridor between rooms $u$ and $v$. It is guaranteed that there are no self-loops.

The first line of output should be either "YES" if the problem has a solution, or "NO" if there is no solution.
If the problem has a solution, the second line should contain an integer $ans$, representing the number of corridors in the constructed path. The third line should contain $ans+1$ integers, representing the sequence of rooms visited in the path,and the path must start at room $1$ and end at room $n$.
If there is no solution, there is no need to output the second and third lines.

NO