DSA Homework 6

GPS

Little John was promoted to Senior Software Engineer. His first project is to write an engine for a next generation GPS device. What he has to do is to implement an algorithm to find the shortest route from the starting point to the destination. The map has already been translated and is represented as a graph where intersections are nodes, and streets and edges. Since some streets are only one-way, this graph is an oriented graph.

Help Little John write this program.

Requirement

Given an oriented graph, find the shortest path between the source node and the destination node.

Input Data

A file called gps.in, containing the number of intersections N on the first line, and N x N subsequent values, defining the adjacency matrix, arranged in a square, on N lines. A value of -1 in the adjacency means that there is no route between those nodes. The last line contains the starting node and the destination node.

Output Data

A file called gps.out, containing the cost of the shortest route (or -1 if there is none) on the first line and the path itself on the second line (the second line is missing if there is no route).

Restrictions

1 ≤ N ≤ 1000

Examples

Input	Output
7 0 -1 1 1 -1 2 -1 3 0 1 -1 -1 -1 -1 -1 2 0 -1 2 -1 -1 -1 -1 -1 0 5 -1 2 -1 -1 2 5 0 -1 -1 -1 -1 -1 -1 -1 0 2 -1 -1 -1 -1 1 -1 0 5 0	10 5 6 4 2 1 0
7 0 -1 1 1 -1 2 -1 3 0 1 -1 -1 -1 -1 -1 2 0 -1 2 -1 -1 -1 -1 -1 0 5 -1 2 -1 -1 -1 5 0 -1 -1 -1 -1 -1 -1 -1 0 2 -1 -1 -1 -1 1 -1 0 5 0	-1