// Port of mjd@cs.auckland.ac.nz CS220 Java graph library into C# .Net
// by r.nicolescu@auckland.ac.nz (Aug'06)

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;

/*
 * Graph implementation using adjacency lists (from CS220 library)
 */
public class Graph {
    // ---------------------------------------------------------------
    //  Internal Representation and Constructors
    // ---------------------------------------------------------------

    private List< List<int> > _adj;   // Vector of Vector of integers.

    private void _allocate(int n) {
        _adj = new List<List<int>>();
        for (int i=0; i<n; i++) _adj.Add(new List<int>());
    }

    public Graph() { // default constructor
        _allocate(0);
    }

    public Graph(Graph G) { // copy constructor
        int n = G.order();
        _adj = new List<List<int>>();
        for (int i=0; i<n; i++) _adj.Add(G.neighbors(i));
    }

    public Graph(TextReader buffer) {
        try {
            string line = buffer.ReadLine().Trim();
            string[] token = Regex.Split(line, @"\s+");
            if (line == "" || token.Length != 1)
                throw new Exception("bad format: number of vertices");

            int n = int.Parse(token[0]);
            _allocate(n);

            for (int u=0; u<n; u++) {
                line = buffer.ReadLine().Trim();
                if (line != "") {
                    token = Regex.Split(line, @"\s+");

                    foreach (string t in token) {
                        int v = int.Parse(t);
                        _adj[u].Add(v);
                    }
                }
            }
        } catch (IOException x) { throw new Exception("bad input stream: "+x); }
    }

    // ---------------------------------------------------------------
    //  Mutator Methods
    // ---------------------------------------------------------------

    public void addVertices(int n) {
        if (n > 0) {
            for (int i=0; i<n; i++) _adj.Add(new List<int>());
        }
    }

    public void removeVertex(int i) {
        _adj.RemoveAt(i);

        for (int u=0; u<order(); u++) {
            List<int> uu = _adj[u];
            uu.Remove(i); // remove i from adj lists

            for (int v=0; v<uu.Count; v++) { // relabel larger indexed nodes
                int nbr = uu[v];
                if (nbr > i) uu[v] = nbr - 1;
            }
        }
    }

    public void addArc(int i, int j) {
        if (isArc(i, j)) return;
        _adj[i].Add(j);
    }

    public void removeArc(int i, int j) {
        _adj[i].Remove(j);
    }

    // ---------------------------------------------------------------
    //  Accessor Methods
    // ---------------------------------------------------------------

    public bool isArc(int i, int j) {
        return _adj[i].Contains(j);
    }

    public int inDegree(int i) {
        int sz = 0;
        for (int j= 0; j<order(); j++) if (isArc(j, i)) sz++;
        return sz;
    }

    public int outDegree(int i) {
        return _adj[i].Count;
    }

    public List<int> neighbors(int i) {
        return new List<int>(_adj[i]);
    }

    public int order() { return _adj.Count; }

    public int size() { // Number of arcs (counts edges twice).
        int sz = 0;
        for (int i=0; i<order(); i++) {
            sz += _adj[i].Count;
        }
        return sz;
    }

    static String EOL = Environment.NewLine;

    // default output readable by constructor
    //
    public String toString() {
        StringBuilder o = new StringBuilder();
        o.Append(order());
        o.Append(EOL);

        for (int i=0; i<order(); i++) {
            for (int j=0; j<order(); j++) {
                if (isArc(i, j)) {
                    o.Append(j);
                    o.Append(" ");
                }
            }
            o.Append(EOL);
        }
        return o.ToString();
    }
}