In an undirected graph, you need to find the minimum path between two vertices.
Input:
- the first line contains the number N - the number of vertices in the graph (\(1<=N<=100\));
- the next lines set the adjacency matrix (0 means no edge, 1 - edge);
- the last line contains numbers of two vertices - initial and final.
Output: print first L - the length of the path (number of edges to pass). Then print < code>L+1 number - vertices in order along this path. If the path does not exist, print a single number -1.
Examples
| # |
Input |
Output |
| 1 |
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
|
3
3 2 1 5
|