import java.lang.IllegalArgumentException;
import java.lang.ref.WeakReference;
import java.lang.StringBuilder;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.Vector;
import java.util.WeakHashMap;

public final class Gr {
    static {
        rng = new Random();
        rngChars = new char[] { 'a', 'b', 'c', 'd', 'e', 'f',
                    'g', 'h', 'i', 'j', 'k', 'l',
                    'm', 'n', 'o', 'p', 'q', 'r',
                    's', 't', 'u', 'v', 'w', 'x',
                    'y', 'z'};
    }

    private Gr() {
    }

    public static interface Graph {
        public void marker(GraphImpl impl);
    }

    private final static class GraphImpl implements Graph {
        public void marker(GraphImpl impl) {
        }

        public final HashSet<Node> nodes = new HashSet<>();
    }

    public static interface Node {
        public void marker(NodeImpl impl);
    }

    private final static class NodeImpl implements Node {
        {
            to = new WeakHashMap<>();
            from = new WeakHashMap<>();
        }

        public void marker(NodeImpl impl) {
        }

        public NodeImpl(String label) {
            this.label = label;
        }

        public final WeakHashMap<Node, Integer> to;
        public final WeakHashMap<Node, Void> from;
        public WeakReference<GraphImpl> owner;
        public String label;
    }

    public static Graph newGraph() {
        return new GraphImpl();
    }

    public static Node newNode(String label) {
        return new NodeImpl(label);
    }

    public static void add(Graph graph, Node node) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        final NodeImpl nodeImpl = (NodeImpl)node;

        if (nodeImpl.owner != null) {
            throw new IllegalArgumentException("Already owned node");
        }
        nodeImpl.owner = new WeakReference<>(graphImpl);
        graphImpl.nodes.add(nodeImpl);
    }

    public static void link(Graph graph, Node a, Node b, int weight) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        NodeImpl aImpl = (NodeImpl)a;
        NodeImpl bImpl = (NodeImpl)b;

        if (aImpl == bImpl) {
            throw new IllegalArgumentException("Two same nodes");
        }
        if (aImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }
        if (bImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        if (aImpl.hashCode() < bImpl.hashCode()) {
            final NodeImpl tmp = aImpl;
            aImpl = bImpl;
            bImpl = tmp;
        }

        if (null == aImpl.to.put(bImpl, weight)) {
            bImpl.from.put(aImpl, null);
        }
    }

    public static boolean connectsTo(Graph graph, Node a, Node b) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        NodeImpl aImpl = (NodeImpl)a;
        NodeImpl bImpl = (NodeImpl)b;

        if (aImpl == bImpl) {
            return true;
        }
        if (aImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }
        if (bImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        if (aImpl.hashCode() < bImpl.hashCode()) {
            final NodeImpl tmp = aImpl;
            aImpl = bImpl;
            bImpl = tmp;
        }

        return aImpl.to.containsKey(bImpl);
    }

    public static int weight(Graph graph, Node a, Node b) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        NodeImpl aImpl = (NodeImpl)a;
        NodeImpl bImpl = (NodeImpl)b;

        if (aImpl == bImpl) {
            return 0;
        }
        if (aImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }
        if (bImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        if (aImpl.hashCode() < bImpl.hashCode()) {
            final NodeImpl tmp = aImpl;
            aImpl = bImpl;
            bImpl = tmp;
        }

        Integer result = aImpl.to.get(bImpl);
        if (null == result) {
            throw new IllegalArgumentException("Node not not an edge");
        }
        return result;
    }

    public static void unlink(Graph graph, Node a, Node b) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        NodeImpl aImpl = (NodeImpl)a;
        NodeImpl bImpl = (NodeImpl)b;

        if (aImpl == bImpl) {
            throw new IllegalArgumentException("Two same nodes");
        }
        if (aImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }
        if (bImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        if (aImpl.hashCode() < bImpl.hashCode()) {
            final NodeImpl tmp = aImpl;
            aImpl = bImpl;
            bImpl = tmp;
        }

        aImpl.to.remove(bImpl);
        bImpl.from.remove(aImpl);
    }

    public static Iterable<Node> nodeIterator(Graph graph) {
        return new IterWrapper(graph);
    }

    private final static class IterWrapper implements Iterable<Node> {
        public Iterator<Node> iterator() {
            final GraphImpl graphImpl = (GraphImpl)graph;
            return graphImpl.nodes.iterator();
        }

        public IterWrapper(Graph graph) {
            this.graph = graph;
        }

        Graph graph;
    }

    public static Set<Map.Entry<Node, Integer>> nodeEdges(Graph graph, Node node) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        final NodeImpl nodeImpl = (NodeImpl)node;

        if (nodeImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        return nodeImpl.to.entrySet();
    }

    public static String label(Graph graph, Node node) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        final NodeImpl nodeImpl = (NodeImpl)node;

        if (nodeImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        return nodeImpl.label;
    }

    public static void remove(Graph graph, Node node) {
        final GraphImpl graphImpl = (GraphImpl)graph;
        final NodeImpl nodeImpl = (NodeImpl)node;

        if (nodeImpl.owner.get() != graph) {
            throw new IllegalArgumentException("Wrong owner");
        }

        for (final Node from: nodeImpl.from.keySet()) {
            ((NodeImpl)from).to.remove(nodeImpl);
        }
    }

    private static String randLabel() {
        final int len = 6;
        final StringBuilder builder = new StringBuilder(len);
        for (int ii = 0; ii < len; ++ii) {
            builder.append(rngChars[rng.nextInt(rngChars.length)]);
        }
        return builder.toString();
    }

    private static Graph randGraph() {
        final Graph graph = Gr.newGraph();

        final int nodeCount = 10;
        final Node[] nodes = new Node[nodeCount];

        for (int ii = 0; ii < nodes.length; ++ii) {
            nodes[ii] = Gr.newNode(Gr.randLabel());
        }

        for (int ii = 0; ii < nodes.length; ++ii) {
            Gr.add(graph, nodes[ii]);
        }

        for (int ii = 0; ii < nodes.length * nodes.length; ++ii) {
            Node a;
            Node b;
            for (;;) {
                a = nodes[rng.nextInt(nodes.length)];
                b = nodes[rng.nextInt(nodes.length)];
                if (a != b) {
                    break;
                }
            }
            Gr.link(graph, a, b, rng.nextInt(34) + 1);
        }

        return graph;
    }

    public static void main(String[] args) {
        final Graph graph = randGraph();

        System.out.print("*");
        for (final Node xx : Gr.nodeIterator(graph)) {
            System.out.print("\t");
            System.out.print(Gr.label(graph, xx));
        }
        System.out.println();

        for (final Node yy : Gr.nodeIterator(graph)) {
            final String yyLabel = Gr.label(graph, yy);
            System.out.print(yyLabel);
            for (final Node xx : Gr.nodeIterator(graph)) {
                final int weight;
                if (Gr.connectsTo(graph, xx, yy)) {
                    weight = Gr.weight(graph, xx, yy);
                } else {
                    weight = -1;
                }
                final String weightStr = Integer.toString(weight);
                System.out.print("\t");
                System.out.print(weightStr);
            }
            System.out.println();
        }
    }

    private final static char[] rngChars;
    private final static Random rng;
}