import java.io.File;
import java.io.PrintWriter;
import java.io.FileWriter;
import java.util.Collections;
import java.util.LinkedList;

public class Forwarding {
    static void dieUsage() {
        System.err.println("Usage:");
        System.err.println("java Forwarding <depth> <fanout> [dotfile]");
        System.err.println("(depth and fanout must be integers >= 1)");
        System.exit(1);
    }

    public static void main(String[] argv) {
        int depth = -1;
        int fanout = -1;
        String filename = null;

        if(argv.length >= 2) {
            depth = Integer.parseInt(argv[0]);
            fanout = Integer.parseInt(argv[1]);
        } else dieUsage();

        if(depth < 1 || fanout < 1) dieUsage();

        if(argv.length >= 3) {
            filename = argv[2];
        }

        TreeNode root = new TreeNode();
        root.build(depth, fanout);
        System.out.println(root);

        if(filename != null) {
            root.saveDOT(new File(filename));
        }

        LinkedList<TreeNode> leaves = root.getLeaves(); // these are the HOSTS

        // TODO:
        // Go through each unique pair (src,dst) of leaves, and compute the path from src to dst.
        // For a single path, you can use the Interface class to store each hop on the path (iface can be used for
        // the input interface, and iface2 can be used for the output interface).
    }
}

class Interface {
    int iface;
    TreeNode node;

    private int iface2 = 0;

    Interface(TreeNode node) {
        this(0, node);
    }

    Interface(int iface, TreeNode node) {
        this.iface = iface;
        this.node = node;
    }

    Interface(int iface1, TreeNode node, int iface2) {
        this.iface = iface1;
        this.iface2 = iface2;
        this.node = node;
    }

    int getIface2() {
        return iface2;
    }

    void setIface2(int iface2) {
        this.iface2 = iface2;
    }

    public String toString() {
        String s;

        if(iface2 == 0) s= String.format("(%d->%s)", iface, node.getName());
        else s = String.format("(%d->%s->%d)", iface, node.getName(), iface2);

        return s;
    }
}

class TreeNode {
    private Interface parent;
    int id;
    LinkedList<Interface> children = new LinkedList<Interface>();
    boolean isLeaf;

    private static int routerId;
    private static int hostId;

    TreeNode() {
        this.parent = null;
        this.id = 1;
    }

    TreeNode(TreeNode parent, int id) {
        this(parent, id, false);
    }

    TreeNode(TreeNode parent, int id, boolean isLeaf) {
        this.parent = new Interface(parent);
        this.id = id;
        this.isLeaf = isLeaf;
        updateParent();
    }

    int getChildInterface(TreeNode child) {
        for(Interface i : children) {
            if(child.equals(i.node)) return i.iface;
        }
        return 0;
    }

    TreeNode getParent() {
        return (parent != null ? parent.node : null);
    }

    int getParentInterface() {
        return (parent != null ? parent.iface : 0);
    }

    void addChild(TreeNode n) {
        int i = children.size() + (isLeaf() ? 0 : 1);
        children.add(new Interface(i, n));
        updateParent();
    }

    boolean isLeaf() {
        return isLeaf;
    }

    String getName() {
        return String.format("%s%d", isLeaf() ? "h" : "s", id);
    }

    LinkedList<TreeNode> getLeaves() {
        LinkedList<TreeNode> l = new LinkedList<TreeNode>();

        if(isLeaf()) {
            l.add(this);
        } else {
            for(Interface i : children) {
                l.addAll(i.node.getLeaves());
            }
        }

        return l;
    }

    void build(int depth, int fanout) {
        routerId = id;
        hostId = 0;
        build(this, depth, fanout);
    }

    private static void build(TreeNode root, int depth, int fanout) {
        for(int i = 0; i < fanout; i++) {
            boolean isLeaf = (depth == 1);
            int id = isLeaf ? ++hostId : ++routerId;
            TreeNode n = new TreeNode(root, id, isLeaf);
            root.addChild(n);
            if(!isLeaf) build(n, depth-1, fanout);
        }
    }

    private void updateParent() {
        if(parent != null) {
            if(isLeaf()) parent.iface = 0;
            else parent.iface = children.size()+1;
        }
    }

    public String toString() {
        return toString(0);
    }

    public String toString(int num) {
        String str = "";
        String space = num == 0 ? "" : String.format("%"+num+"s", " ");
        for(Interface i : children) {
            TreeNode n = i.node;
            str += String.format("%s%d->%s,\n", space+"   ", i.iface, n.toString(num+3));
        }
        return String.format("%s{name=%s, parent=%s,\n%s%s}", isLeaf() ? "Host" : "Router", getName(), parent != null ? parent : "None", str, space);
    }

    String toDotString() {
        String s = String.format("%s [];\n", getName());
        for(Interface i : children) {
            s += i.node.toDotString();
            s += String.format("%s -- %s [taillabel=\"%d\", headlabel=\"%d\"];\n", getName(), i.node.getName(), i.iface, i.node.getParentInterface());
        }
        return s;
    }

    void saveDOT(File f) {
        try {
            PrintWriter out = new PrintWriter(new FileWriter(f), true);
            out.println("graph {");
            out.print(toDotString());
            out.println("}");
            out.close();
        } catch(Exception ex) {

        }
    }
}