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 nnn rooms and mmm 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 111. Her goal is to find a path that leads to the endpoint of the maze, which is room number nnn.
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 nnn 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 nnn integers colori(0≤colori≤1)color_i(0\leq color_i \leq 1)colori(0≤colori≤1), representing the colors of each room, 000 indicates blue, and 111 indicates red.
The next mmm lines each contain two integers uuu and v(1≤u,v≤n)v(1 \leq u,v \leq n)v(1≤u,v≤n), representing an undirected corridor between rooms uuu and vvv. 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 ansansans, representing the number of corridors in the constructed path. The third line should contain ans+1ans+1ans+1 integers, representing the sequence of rooms visited in the path,and the path must start at room 111 and end at room nnn.
If there is no solution, there is no need to output the second and third lines.