E. Shortest Non-Shortest Path
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. There are no self-loops and multiple edges in the graph. You have to find any path $$$P$$$ between the specified vertices $$$s$$$ and $$$t$$$ such that:

  1. $$$P$$$ does not contain any vertex of the graph more than once;
  2. $$$P$$$ contains more vertices than the shortest path between $$$s$$$ and $$$t$$$;
  3. $$$P$$$ contains the least number of vertices among all paths that satisfy conditions $$$1$$$ and $$$2$$$.
Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$t$$$ ($$$2 \le n \le 2\,000$$$; $$$n-1 \le m \le 25\,000$$$; $$$1 \le s, t \le n$$$, $$$s\neq t$$$) — the number of vertices and edges in the graph, and the endpoints of the path $$$P$$$, respectively.

The next $$$m$$$ lines describe the edges: edge $$$i$$$ is defined by a pair of vertices $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$), where $$$a_i$$$ and $$$b_i$$$ are the vertices connected by the $$$i$$$-th edge.

It is guaranteed that there are no self-loops and multiple edges in the given graph.

Output

If the desired path $$$P$$$ does not exist, print $$$-1$$$ in a single line.

Otherwise, in the first line, print the number $$$k$$$ — the number of vertices in the path $$$P$$$. In the second line, print $$$k$$$ distinct integers, $$$v_1, v_2, \ldots, v_k$$$ ($$$1\le v_i \le n$$$, $$$v_1=s$$$, $$$v_k=t$$$, $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge for any $$$1 \le i \lt k$$$) — the vertex numbers in the path $$$P$$$.

If there are multiple answers, print any of them.

Examples
Input
3 3 1 2
1 2
2 3
3 1
Output
3
1 3 2
Input
5 4 1 5
1 2
2 3
3 4
4 5
Output
-1