Challenge: Fewest Train Changes

Lab Java Intermediate 20 points

Stations are linked by train lines. Print the fewest number of rides needed to get from station s to station t, or -1 if it's impossible. Use BFS.

Input

Line 1: n m – people/places are numbered 1 to n, and there are m links. Then m lines u v: a two-way link between u and v.

Last line: s t.

Output

The fewest rides, or -1.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

dist[] starts at -1 for every station; dist[s] = 0.

BFS: when you first reach a station, its distance is dist[cur] + 1.

Solution explanation

BFS finds the fewest edges in O(n + m). Stations never reached keep −1.

Show solution

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            g.get(u).add(v);
            g.get(v).add(u);
        }
        int s = sc.nextInt(), t = sc.nextInt();
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
        dist[s] = 0;
        queue.offer(s);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : g.get(cur)) {
                if (dist[next] == -1) {
                    dist[next] = dist[cur] + 1;
                    queue.offer(next);
                }
            }
        }
        System.out.println(dist[t]);
    }
}

Output

Answer