import java.util.ArrayList;

public class Graph {

    private ArrayList<Vertex> vertices;

    public Graph() {
        this.vertices = new ArrayList<Vertex>();
    }

    public int size() {
        return this.vertices.size();
    }

    public Vertex getVertex(int i) {
        if (i >= this.size())
            throw new IndexOutOfBoundsException("Specified vertex index is out of range.");

        return this.vertices.get(i);
    }

    public int addVertex(String w) {
        this.vertices.add(
                new Vertex(this.vertices.size(), w));

        return (this.vertices.size() - 1);
    }

    public void initAdjacencyLists() {
        for (Vertex v : this.vertices)
            for (Vertex w : this.vertices)
                if (Graph.areVerticesAdjacent(v, w))
                    v.addToAdjacencyList(w);
    }

    private static boolean areVerticesAdjacent(Vertex v, Vertex w) {
        String vWord = v.getWord();
        String wWord = w.getWord();

        if (vWord.length() != wWord.length())
            return false;

        if (vWord.equals(wWord))
            return false;

        int differenceCount = 0;

        for (int i = 0; i < vWord.length(); i++)
            if (vWord.charAt(i) != wWord.charAt(i))
                differenceCount++;

        if (differenceCount != 1)
            return false;

        return true;
    }

    public void doBusiness(int w1index, int w2index) {

        ArrayList<Vertex> q = this.vertices;
        //ArrayList<Vertex> pred = new ArrayList<Vertex>();

        Vertex u = q.get(w1index);
        u.distance = 0;
        q.remove(u);

        for (Vertex v : this.vertices) {
            if (Graph.areVerticesAdjacent(u, v))
                v.distance = dist_between(u, v);
        }

        ArrayList<Vertex> S = new ArrayList<Vertex>();
        S.add(u);

        while (!q.isEmpty()) {

            Vertex v = getSmallest(q);
            S.add(v);
            q.remove(v);

            for (Vertex w : q) {
                int dist = dist_between(v, w);
                w.distance = dist;
            }

        }

    }

    private static Vertex getSmallest(ArrayList<Vertex> list) {

        Vertex v = null;
        int s = Integer.MAX_VALUE;

        for (Vertex w : list) {

            if (w.distance < s) {
                v = w;
                s = w.distance;
            }

        }

        list.remove(v);

        return v;
    }

    private static int dist_between(Vertex u, Vertex v) {
        String word1 = u.getWord();
        String word2 = v.getWord();
        char a = 0;
        char b = 0;

        for (int i = 0; i < word1.length(); i++) {
            a = word1.charAt(i);
            b = word2.charAt(i);

            if (a < b)
                return b - a;
            else if (a > b)
                return a - b;
        }

        return 0;
    }

}