public class mTreeS<A> : extends mTree<A> {
    protected int outDegree;

    public void newEmpty() {
        super.newEmpty();
        outDegree = 0;
    }

    public void newVertex(A r) {
        super.newVertex(r);
        outDegree = 0;
    }

    public void addEdge(A r, A s) throws Exception {
        super.addEdge(r, s);
        int sons = super.sons(r).size();
        if (sons > outDegree) outDegree = sons;
    }

    public int fanOut() { return outDegree; }
}

public class mTreeR<A> : extends mTreeS<A> {
    private class Pair<A> {
        public A fst;
        public A snd;
        public Pair(A x, A y) {
            this.fst = x;
            this.snd = y;
        }
    }

    private class PairDegree<A> {
        public A node;
        public int degree;
        public PairDegree(A x, int y) {
            this.node = x;
            this.degree = y;
        }
    }

    private Vector<Pair<A>> removed;
    private Vector<PairDegree<A>> degrees;

    private void checkDegree() {
        int max = -1;
        for (PairDegree<A> pd : degrees) {
            if (pd.degree > max) max = pd.degree;
        }
        this.outDegree = max;
    }

    public mTreeR() {
        super();
        removed = new Vector<Pair<A>>();
        degrees = new Vector<PairDegree<A>>();
    }

    public void newEmpty() {
        super.newEmpty();
        removed = new Vector<Pair<A>>();
        degrees = new Vector<PairDegree<A>>();
    }

    public void newVertex(A r) {
        super.newVertex(r);
        removed = new Vector<Pair<A>>();
        degrees = new Vector<PairDegree<A>>();
        degrees.add(new PairDegree<A>(r, 0));
    }

    public void addEdge(A r, A s) throws Exception {
        Pair<A> ref = null;
        for (Pair<A> p : removed) {
            if (p.fst.equals(r) && p.snd.equals(s)) ref = p;
        }
        if (ref == null) super.addEdge(r, s);
        else removed.remove(ref);

        degrees.add(new PairDegree<A>(s, 0));
        for (PairDegree<A> pd : degrees) {
            if (pd.node.equals(r)) pd.degree++;
        }

        checkDegree();
    }

    public void remove(A r, A s) throws Exception {
        Pair<A> ref = null;
        for (Pair<A> p : removed) {
            if (p.fst.equals(r) && p.snd.equals(s)) ref = p;
        }
        if (ref != null) throw new Exception("Error");

        boolean found = false;
        for (A a : super.sons(r)) if (a.equals(s)) found = true;
        if (!found) throw new Exception("Error");

        removed.add(new Pair<A>(r, s));
        for (PairDegree<A> pd : degrees) {
            if (pd.node.equals(r)) pd.degree--;
        }
        checkDegree();

    }

    public Vector<A> sons(A r) throws Exception {
        Vector<A> s = super.sons();
        Vector<A> res = new Vector<A>();
        for (A a : s) {
            boolean found = false;
            for (Pair<A> p : removed) {
                if (p.fst.equals(r) && p.snd.equals(a)) found = true;
            }
            if (!found) res.add(a);
        }
        return res;
    }
}