import java.util.Vector;
import javax.swing.JOptionPane;

class ControleNo {
    
    public ControleNo(String n, String p, int l) {
        no = n;
        pai = p;
        nivel = l;
    }

    private String no;
    private String pai;
    private int nivel;

    public String getNo() {return no;}
    public void setNo(String no) {this.no = no;}
    public String getPai() {return pai;}
    public void setPai(String pai) {this.pai = pai;}
    public int getNivel() {return nivel;}
    public void setNivel(int nivel) {this.nivel = nivel;}
}

public class Busca {
    
    public Busca() {}
    
    public static boolean eRepetido (int i, Vector <ControleNo> aux, String possivelCidade) {
        for (int z=0;z<=i;z++) {
            if (aux.get(z).getNo() == possivelCidade) {
                if (aux.get(z).getNivel() <= i+1) {
                    return true;
                }
            }                
        }
        return false;
    }
    
    public static Vector amplitude(Estado e, String inicial, String objetivo) {
        
        Vector v = new Vector();
        
        Vector <ControleNo> no = new Vector<ControleNo>(1);
        no.add(new ControleNo(inicial, "", 0));
        
        int i = 0;
        while (i<no.size()) {
            if (no.get(i).getNo() == objetivo) break; // verifica se chegou onde queria
            for (int j=0; j < e.v.size();j++) {
                if (no.get(i).getNo() == e.v.get(j).getCidEsq() && !eRepetido(i,no,e.v.get(j).getCidDir())) {
                    no.add(new ControleNo(e.v.get(j).getCidDir(),no.get(i).getNo(),i+1));
                }
                if (no.get(i).getNo() == e.v.get(j).getCidDir() && !eRepetido(i,no,e.v.get(j).getCidEsq())) {
                    no.add(new ControleNo(e.v.get(j).getCidEsq(),no.get(i).getNo(),i+1));
                }
            }
            i++;
        }
        v.add(no.get(i).getNo());
        v.add(no.get(i).getPai());
        while (no.get(i).getPai() != "") {
            /* O GRANDE PROBLEMA ESTÁ AQUI!      
             * NÃO SEI RESOLVER :(   */
        }
        
        java.util.Collections.reverse(v);
        return v;
    }
}