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


            // Go through each unique pair (src,dst) of leaves, and compute the path from src to dst.

  public void printAllPaths(int src, int dst)
    {
        boolean[] isVisited = new boolean[v];
        ArrayList<Integer> pathList = new ArrayList<>();

        //add source to path[]
        pathList.add(s);

        //Call recursive utility
        printAllPathsUtil(src, dst, isVisited, pathList);
    }

            // 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) {

            }
        }
    }