CF2249F Even Simple Path

You are given a simple undirected graph with $ n $ vertices and $ m $ edges. A path is simple if it visits no vertex more than once. The length of a path is the number of edges in it. Find a shortest simple path with even length from vertex $ 1 $ to vertex $ n $ , or determine that no such path exists.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2\le n\le 1000 $ , $ 0\le m\le \frac{n(n-1)}2 $ ) — the number of vertices and the number of edges in the graph. Then $ m $ lines follow, the $ i $ -th line containing two integers $ u_i $ and $ v_i $ ( $ 1\le u_i,v_i\le n $ , $ u_i\ne v_i $ ) — the two vertices that the $ i $ -th edge connects. It is guaranteed that there are no self-loops or multiple edges in the graph. It is guaranteed that the sum of $ n^3 $ over all test cases does not exceed $ 1000^3 $ . It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 10^6 $ .

For each test case, if no such path exists, print $ -1 $ . Otherwise, print any shortest simple path of even length from vertex $ 1 $ to vertex $ n $ : - On the first line, print its length $ k $ ; - On the second line, print $ k+1 $ vertices $ p_0,p_1,\ldots,p_k $ in order, where $ p_0=1 $ and $ p_k=n $ . If there are multiple possible answers, you may print any of them.

In the first test case, there is no path from vertex $ 1 $ to vertex $ 2 $ , so there is no answer. In the second test case, the path $ 1 \to 2 \to 3 $ has length $ 2 $ , and it is the shortest simple path with even length. In the third test case, the only simple path from vertex $ 1 $ to vertex $ 4 $ has length $ 3 $ , which is not even, so there is no answer. In the fourth test case, the path consisting only of the edge $ 1 \to 5 $ has length $ 1 $ , which is odd and cannot be an answer. The path $ 1 \to 2 \to 5 $ has length $ 2 $ . In the fifth test case, the path $ 1 \to 2 \to 3 \to 4 \to 6 $ has length $ 4 $ , while the path $ 1 \to 6 $ has length $ 1 $ , which is not even.