import java.util.*;
import java.io.*;
import java.net.*;

public class LagrangeAgent {

	public static final String IDENT = "anti60";

	public static final int RUNS = 100;

	public static final int TIME_LIMIT = 1000;

	public static final int TIME_TICK = 100;

	public static final int SET_SIZE = 60;

	public BrainStore brain;
    
	public int degree = 1;
	public final int numberOfAgents;
	public final int sensor;
	public final int desired;

	public LagrangeAgent [] world;
	public int [] messageQueue;
	public boolean [] neighbour;
	public int lastUseful = -1;
	public boolean [] allUseful = new boolean [SET_SIZE];
	public int numUseful = 0;
	private int index;
	private boolean done = false;
	private Random random;
    
	/**
	Constructor -- creates LagrangeAgent.
	*/
	public LagrangeAgent (LagrangeAgent [] w, int i, int n, int limit, double irrat, Random r) throws GraphException {
		index = i;
		world = w;
		random = r;
		int inx = (23 * i) % n;
		
		if (n == 60) {
			sensor = inx;   			//  0..59, if n==60
			desired = (inx / 2) + 33;	// 33..62, if n==60
			brain = new LagrangeStore (desired, limit, r, irrat);
							
		} else throw new GraphException ("LagrangeAgent not set up for " + n);

		
		numberOfAgents = n;

		messageQueue = new int [n];
		for (int j = 0; j < numberOfAgents; j++) {
			messageQueue [j] = -1;
		}
		neighbour = new boolean [n];
		tryANumber (sensor);
	}

	/**
	Send a message
	*/
	public boolean send (int num, int to) throws GraphException {
		world [to].messageQueue [index] = num;
		return true;
	}

	/**
	Try a number, return whether it was useful.
	*/
	public boolean tryANumber (int num) throws GraphException {
		boolean useful = brain.tryNumber (num);
		if (useful) {
			addANumber (num);
		}
		if (brain.getSuccess ()) done = true;
		return useful;
	}
	
	/**
	Add a useful number.
	*/
	public void addANumber (int num) throws GraphException {
		lastUseful = num;
		if (! allUseful [num]) {
			allUseful [num] = true;
			numUseful++;
		}
	}
	
	/**
	Get a useful number.
	*/
	public int getANumber () throws GraphException {
		if (numUseful == 0) return sensor;
		int j = (int) (numUseful * random.nextDouble ());
		int k = -1;
		int inx = -1;
		while (k < j) {
			inx++;
			if (allUseful [inx]) k++;
		}
		return inx;
	}
	
	/**
	Do tick -- send
	*/
	public void sendPhase () throws GraphException {
		int num = getANumber ();
		for (int i = 0; i < numberOfAgents; i++) {
			if (neighbour [i]) send (num, i);
		}
	}
	
	/**
	Do tick -- receive
	*/
	public void receivePhase () throws GraphException {
		for (int i = 0; i < numberOfAgents; i++) {
			int j = i;
			int num = messageQueue [j];
			messageQueue [j] = -1;
			if (num >= 0) {
				boolean suc = tryANumber (num);
			}
		}
	}


	/**
	Do tick
	*/
	public static boolean tick (int start, LagrangeAgent [] w, int n) throws GraphException {
		for (int i = 0; i < n; i++) {
			w [(start + i) % n].sendPhase ();
		}
		for (int i = 0; i < n; i++) {
			w [(start + i) % n].receivePhase ();
		}
		boolean alldone = true;
		for (int i = 0; i < n; i++) {
			if (! w [i].done) alldone = false;
		}
		return alldone;
	}
				
	/**
	Run: return time taken for success, or number of failures (coded negative)
	*/
	public static long run (LagrangeAgent [] w, int n, Random r) throws GraphException {
		long t = 0;
		boolean finished = false;
		while (t < TIME_LIMIT && ! finished) {
			int start = (int) (n * r.nextDouble ());
			tick (start, w, n);
			finished = true;
			for (int i = 0; i < n; i++) {
				if (! w [i].done) finished = false;
			}
			t++;
			if (t % TIME_TICK == 0) {
				int tot = 0;
				for (int i = 0; i < n; i++) {
					if (w [i].done) tot++;
				}
				System.err.println ("Tick " + t + " " + (tot * 100.0 / n) + "%");
			}
		}
		int fails = 0;
		for (int i = 0; i < n; i++) {
			if (! w [i].done) fails++;
		}
		if (fails > 0 && t < TIME_LIMIT) throw new GraphException ("Failure test bug");
		return t < TIME_LIMIT ? t : -fails;
	}

				
	/**
	Setup
	*/
	public static LagrangeAgent [] setup (Graph g, int n, int limit, double irrat, Random r) throws GraphException {
		LagrangeAgent [] w = new LagrangeAgent [n];
		for (int i = 0; i < n; i++) {
			w [i] = new LagrangeAgent (w, i, n, limit, irrat, r);
		}
		for (int i = 0; i < n; i++) {
			Node node = g.getNode (i);
			Vector edges = g.edgesFrom (node);
			w[i].degree = edges.size ();
			Enumeration en = edges.elements ();
			
			while (en.hasMoreElements ()) {
				Edge edge = (Edge) en.nextElement ();
				int j = g.getIndex (edge.getTo ());
				w[i].neighbour [j] = true;
				w[j].neighbour [i] = true;
			}			
		}
		return w;
	}

	/**
	Go
	*/
	public static long runOne (Graph g, int n, int limit, double irrat, Random r) throws GraphException {
		LagrangeAgent [] w = setup (g, n, limit, irrat, r);
		return run (w, n, r);
	}


	/**
	Go
	*/
	public static long runOne (Graph g, int limit, double irrat, Random r) throws GraphException {
		int n = g.getNodeCount();
		return runOne (g, n, limit, irrat, r);
	}


	/**
	Go
	*/
	public static long runOne (Graph g, int limit, double irrat) throws GraphException {
		return runOne (g, limit, irrat, new Random (System.currentTimeMillis ()));
	}

	
	public static void runOne (String id, double prob, double aved, Graph g, int limit, double irrat, double clus, double avenc, int run, PrintStream out) throws IOException, GraphException {
		long t = runOne (g, limit, irrat);
		out.println (prob + "\t" + aved + "\t" + clus + "\t" + avenc + "\t" + irrat + "\t" + t);
		out.flush ();
	}

	
	public static void runLoop (String id, double prob, Graph g, int limit, int run, PrintStream out) throws GraphException, IOException, GraphException {
		//
		// Network attribute calculations
		//
		double aved = g.aveDistance ();
		double clus = g.clusterCoeff ();
    	double avenc = g.averageNodeConnectivity ();
    	
		double [] irrats = new double [] {0, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3};
		for (int i = 0; i < irrats.length; i++) {
			double irrat = irrats [i];
			runOne (id, prob, aved, g, limit, irrat, clus, avenc, run, out);
		}
	}

	
	public static void runLoop (String id, Graph g, int run, PrintStream out) throws GraphException, IOException, GraphException {
		int limit = 1000;
       	double [] probs = new double [] {0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 5}; 

       	for (int i = 0; i < probs.length; i++) {
			double prob = probs [i];
			Random random = new Random (System.currentTimeMillis ());
			//
			// Network rewiring calculations
			//
			Graph h = (Graph) g.clone ();
			boolean problemFound = h.rewire (prob, random);

			while (problemFound || !  h.isConnected ()) {
				System.err.println ("Retrying...");
				h = (Graph) g.clone ();
				problemFound = h.rewire (prob, random);
			}
			runLoop (id, prob, h, limit, run, out);
        }
	}

	
	public static void main (String[] args) throws IOException, GraphException {
		BufferedReader in = new BufferedReader (new FileReader (IDENT + ".txt"));
        System.err.println ("Reading " + IDENT + ".txt");
        Graph g = Graph.read (in);
        
		for (int i = 0; i < RUNS; i++) {
			runLoop (IDENT, g, i, System.out);
		}
	}
}


abstract class BrainStore {

	public final int desired;
	public final Random random;
	public final double irrationality;
	
	public boolean success = false;
	public String successString = null;

	public BrainStore (int des, Random r, double irr) {
		random = r;
		desired = des;
		irrationality = irr;
	}
	
	public abstract boolean tryNumber (int sq) throws GraphException; // return useful

	public boolean getSuccess () {
		return success;
	}

	public String getSuccessString () {
		return successString;
	}

}


class LagrangeStore extends BrainStore {

	private final int limit;
	private int [] sums;
	private int [] nums;
	private String [] data;
	private int size = 0;
	private Hashtable index = new Hashtable ();
	
	public int getSize () {
		return size;
	}

	public LagrangeStore (int des, int lim) {
		this (des, lim, null, 0);
	}

	public LagrangeStore (int des, int lim, Random r, double irr) {
		super (des, r, irr);
		limit = lim;
		sums = new int [limit];
		nums = new int [limit];
		data = new String [limit];
		put (0, 0, "");
	}

	private boolean put (int sum, int num, String s) { // returns OK
		if (success) return true;
		if (size == limit) return false;
		String label = sum + ":" + num;
		if (index.get (label) != null) return true;
		int i = size;
		size ++; 
		sums [i] = sum;
		nums [i] = num;
		data [i] = s;
		index.put (label, new Integer (i));
		return true;
	}

	private boolean tryAux (int sq) { // return new success
		if (success) return false;
		int root = (int) Math.round (Math.sqrt (sq));
		if (sq != root * root) return false;
		int m = size;
		String extra = "" + sq;
		
		for (int j = 1; j <= 4; j++) {
			for (int i = 0; i < m; i++) {
				int sum = sums [i] + j * sq;
				int num = nums [i] + j;
				String s = (nums [i] == 0 ? "" : data [i] + "+") + extra;
				
				if (num == 4 && sum == desired) {
					success = true;
					successString = s + " = " + desired;
					//System.err.println ("... success: " + s);
					return true;
				} else if (num >= 4 || sum > desired) {
					// ignore
				} else {
					put (sum, num, s);
				}
			}
			extra = extra + "+" + sq;
		}
		return false;
	}


	public boolean tryNumber (int sq) { // return useful
		if (success) return false;
		
		int m = size;
		tryAux (sq);
		boolean useful = (success || size > m);
		//if (useful) System.err.println ("... really useful: " + sq);
		
		if (irrationality == 0) {
			return useful;
		} else {
			boolean wrong = random.nextDouble () < irrationality;
			return wrong ? (! useful) : useful;
		}
	}
}


//////////////////////////////////////////
//										//
// Cut-down version of Network package  //
//										//
//////////////////////////////////////////

class GraphException extends Exception {

    public GraphException() {
	    super();
    }

    public GraphException(String s) {
	    super(s);
    }

    public GraphException(Exception ex) {
	    super(ex instanceof GraphException ? ex.getMessage () : ex.toString ());
        ex.printStackTrace (System.err);
    }
}

class Node {

    private final String name;

    public Node (String n) {
        name = n;
    }

    /** 
    Return name of a graph element.
    */
    public String getName () {
        return name;
    }

    public String toString () {
        return name;
    }
}

class Edge {

    private final Node from;
    private final Node to;
    private Edge inv = null;

    public String toString () {
        return from + " --- " + to;
    }

    private Edge (Node f, Node t) {
        from = f;
        to = t;
    }

    public void setInv () {
        if (inv == null) {
        	Edge e = new Edge (to, from);
        	inv = e;
        	e.setInv (this);
        }
        	
    }

    private void setInv (Edge e) {
        inv = e;	
    }

    public Edge getInv () {
        return inv;	
    }

    public static Edge create (Node f, Node t, Graph g) throws GraphException {
    	Edge e = new Edge (f, t);
    	e.setInv ();
    	g.addEdge (e);
    	return e;
    }

    public static Edge create (String s, Graph g) throws GraphException {
    	int i = s.indexOf ("\t");
    	Node from = g.getNode (s.substring (0, i));
    	Node to = g.getNode (s.substring (i+1));
    	return create (from, to, g);
    }

    /** 
    Where does this edge come from?
    */
    public Node getFrom () {
        return from;
    }

    /** 
    Where does this edge go to?
    */
    public Node getTo () {
        return to;
    }
}


class Graph implements Cloneable {

	public static final int KAWACHI_CONSTANT = 10;

    private int nodecount = 0;
    private Vector nodes = new Vector ();
    private Vector edges = new Vector ();
    private Hashtable nodelookup = new Hashtable ();
    private Hashtable nodeindex = new Hashtable ();
    private Hashtable adj = new Hashtable ();
    private Hashtable revadj = new Hashtable ();
    
    /** 
    Create a graph.
    */
    public Graph () {
    }

    /** 
    Create a graph.
    */
    public Graph (Vector n, Vector e) {
    	nodecount = n.size ();
    	nodes = (Vector) n.clone ();
    	edges = (Vector) e.clone ();
   		rebuildAdj ();
    }

    public Object clone () {
        return new Graph (nodes, edges);
    }

    /** 
    Return a vector of all the nodes in the graph.
    */
    public Vector getAllNodes () {
        return nodes;
    }

    /** 
    Return a vector of all the edges in the graph.
    */
    public Vector getAllEdges () {
        return edges;
    }
        
    /** 
    Return the Node object with a specific name.
    */
    public Node getNode (String name) {
        Node node = (Node) nodelookup.get (name);
        if (node != null) {
            return node;
        } else {
        	Node n = new Node (name);
        	nodes.addElement (n);
        	nodeindex.put (n, new Integer (nodecount));
        	nodecount++;
        	nodelookup.put (name, n);
            return n;
        }
    }
        
    /** 
    Return the Node object with a specific index.
    */
    public Node getNode (int i) {
        return (Node) nodes.elementAt (i);
    }
        
    /** 
    Return the index of a Node object.
    */
    public int getIndex (Node n) {
        return ((Integer) nodeindex.get (n)).intValue ();
    }
        
    /** 
    How many nodes does this graph contain?
    */
    public int getNodeCount () {
        return nodecount;
    }

	public double clusterCoeff () {
		int n = getNodeCount();
		double total = 0;
		for (int i = 0; i < n; i++) {
			boolean [] neigh = neighbourhood (this, i);
			total += clusterCount (this, neigh);
		}
		return total/n;
	}

	public double averageNodeConnectivity () {
		// not ported to this version
		return 0;
	}

    public int diameter () {
        double [] [] distances = shortestPathDistance ();
        double diam = 0;
        for (int i = 0; i < nodecount; i ++) {
            for (int j = i+1; j < nodecount; j ++) {
                if (distances [i] [j] > diam) diam = distances [i] [j];
            }
        }
        return (int) Math.round (diam);
    }
    
    public double aveDistance () {
        double [] [] distances = shortestPathDistance ();
        double total = 0;
        int count = 0;
        for (int i = 0; i < nodecount; i ++) {
            for (int j = i+1; j < nodecount; j ++) {
                double d = distances [i] [j];
                total += d;
                count++;
            }
        }
        return total/count;
    }
    
    private void rebuildAdj () {
    	Enumeration enumeration = edges.elements ();
        while (enumeration.hasMoreElements ()) {
            Edge edge = (Edge) enumeration.nextElement ();
    		addAdjacency (edge.getFrom (), edge, false);
    		addAdjacency (edge.getTo (), edge.getInv (), true);
        }
    	enumeration = nodes.elements ();
    	int i = 0;
        while (enumeration.hasMoreElements ()) {
            Node node = (Node) enumeration.nextElement ();
            nodeindex.put (node, new Integer (i));
            i++;
            nodelookup.put (node.getName (), node);
        }
    }
    
    private void addAdjacency (Node n, Edge edge, boolean rev) {
    	Hashtable h = rev ? revadj : adj; 
    	Vector v = (Vector) adj.get (n);
    	if (v == null) {
    		v = new Vector ();
    		h.put (n, v);
    	}
        v.addElement (edge);
    }
    
    public void addEdge (Edge edge) throws GraphException {
    	if (edge.getFrom() == edge.getTo()) {
            System.err.println ("Ignoring circular edge " + edge);
            return;
        }
        Edge x = edgeBetween (edge.getFrom(), edge.getTo());
        if (x != null) {
            System.err.println ("Ignoring duplicate edge " + edge);
            return;
        }
        x = edgeBetween (edge.getTo(), edge.getFrom());
        if (x != null) {
            System.err.println ("Ignoring duplicate (inv) edge " + edge);
            return;
        }
    	addAdjacency (edge.getFrom (), edge, false);
    	addAdjacency (edge.getTo (), edge.getInv (), true);
    	edges.addElement (edge);
    }
    
    private void removeAdjacency (Node n, Edge edge, boolean rev) {
    	Hashtable h = rev ? revadj : adj; 
    	Vector v = (Vector) adj.get (n);
    	if (v == null) {
    		v = new Vector ();
    		h.put (n, v);
    	}
        v.removeElement (edge);
    }
    
    public void deleteEdge (Edge edge) {
    	removeAdjacency (edge.getFrom (), edge, false);
    	removeAdjacency (edge.getTo (), edge.getInv (), true);
    	edges.removeElement (edge);
    }
    
    /** 
    Return the vector of edges from (or if flipped, to) this node.
    */
    public Vector edgesFrom (Node node, boolean flip) {
        if (flip) return edgesTo (node);
        else return edgesFrom (node);
    }
    
    /** 
    Return the vector of edges from this node.
    */
    public Vector edgesFrom (Node node) {
        return (Vector) adj.get (node);
    }
    
    /** 
    Return the vector of edges to this node.
    */
    public Vector edgesTo (Node node) {
        return (Vector) revadj.get (node);
    }
    
    /** 
    Return the degree of this node.
    */
    public int degree (Node node) {
        return edgesFrom (node).size ();
    }
    
    /** 
    Return the edge between two nodes, or null if there is no such edge.
    For the purposes of this method, it is assumed that there is only one such edge.
    */
    public Edge edgeBetween (Node from, Node to) {
        Vector edges = edgesFrom (from);
        if (edges == null) return null;
        Enumeration enumeration = edges.elements ();
        while (enumeration.hasMoreElements ()) {
            Edge edge = (Edge) enumeration.nextElement ();
            if (edge.getTo() == to) return edge;
        }
        return null;
    }

    /** 
    Return a matrix of edges between nodes (matrix [i] [j] is from node i --> node j).
    For the purposes of this method, it is assumed that there is only one such edge.
    */
    public Edge [] [] matrix () {
        Edge [] [] m = new Edge [nodecount] [nodecount];
        for (int i = 0; i < nodecount; i ++) {
            for (int j = 0; j < nodecount; j ++) {
                m [i] [j] = null;
            }
        }

        Enumeration enumeration = edges.elements ();
        while (enumeration.hasMoreElements ()) {
            Edge edge = (Edge) enumeration.nextElement ();
            Node from = edge.getFrom ();
            Node to = edge.getTo ();
            m [getIndex (from)] [getIndex (to)] = edge;
        }
        return m;
    }

    public boolean isConnected () {
        double [] [] distances = shortestPathDistance ();
        for (int i = 0; i < nodecount; i ++) {
            for (int j = i+1; j < nodecount; j ++) {
                if (distances [i] [j] >= Float.MAX_VALUE) return false;
            }
        }
        return true;
    }

    public double [] [] shortestPathDistance () {
        double [] [] distances = new double [nodecount] [nodecount];
        for (int i = 0; i < nodecount; i ++) {
            for (int j = 0; j < nodecount; j ++) {
                distances [i] [j] = (i == j) ? 0.0 : Float.MAX_VALUE;
            }
        }            
        Enumeration enumeration = getAllEdges ().elements ();
        while (enumeration.hasMoreElements ()) {
            Edge edge = (Edge) enumeration.nextElement ();
            int i = getIndex (edge.getFrom ());
            int j = getIndex (edge.getTo ());
            if (i != j) {
                if (distances [i] [j] > 1) {
                    distances [i] [j] = 1;
                    distances [j] [i] = 1;
                }
            }
        }
        for (int k = 0; k < nodecount; k ++) {
            for (int i = 0; i < nodecount; i ++) {
                for (int j = 0; j < nodecount; j ++) {
                    double d = distances [i] [k] + distances [k] [j];
                    if (d < distances [i] [j]) {
                        distances [i] [j] = d;
                    }
                }
            }
        }
        return distances;
    }

    public boolean rewire (double p, Random r) throws GraphException {
    	return rewireKawachi (p, this, r) <= 0;
    }


    public static int rewire (boolean watts, double prob, Graph g, Random random) throws GraphException {
		if (watts) return rewireWatts (prob, g, random);
		else return rewireKawachi (prob, g, random);
    }
    
    public static int rewireKawachi (double prob, Graph g, Random random) throws GraphException {
    	int res = 0;
    	for (int i = 0; i < KAWACHI_CONSTANT; i++) {
    		res += rewireKawachiAux (prob/KAWACHI_CONSTANT, g, random);
    	}
    	return res;
    }
    	
    public static int rewireKawachiAux (double prob, Graph g, Random random) throws GraphException {
    	int n = g.getNodeCount();
    	if (n < 3) throw new GraphException ("Too few nodes for rewiring");
    	Vector edges = g.getAllEdges();
    	int sz = edges.size();
    	if (sz < 1) throw new GraphException ("Too few edges for rewiring");

    	Vector toDelete = new Vector();
    	int deleteCount = 0;
    	Enumeration enumeration = edges.elements ();
    	while (enumeration.hasMoreElements ()) {
			Edge edge = (Edge) enumeration.nextElement ();
			if (random.nextDouble () < prob) {
				toDelete.addElement (edge);
				deleteCount++;
			}
    	}

		Vector problemNodes = new Vector();
		
		System.err.println ("Deleting a batch of " + (toDelete.size ()) + " edges");
    	enumeration = toDelete.elements ();
    	while (enumeration.hasMoreElements ()) {
			Edge edge = (Edge) enumeration.nextElement ();
			// delete one-by-one
			g.deleteEdge (edge);
    		if (g.getAllEdges().size() != sz-1) throw new GraphException ("Oops! Rewiring delete failed.");

    		int deg1 = g.degree (edge.getFrom());
    		int deg2 = g.degree (edge.getTo());

    		if (deg1 == 1) problemNodes.addElement (edge.getFrom());
    		if (deg2 == 1) problemNodes.addElement (edge.getTo());
    		
    		Node z = null;
    		if (problemNodes.size () > 0) {
    			z = (Node) problemNodes.elementAt (0);
    			//System.err.println ("Problem node " + z);
    			problemNodes.removeElementAt (0);
    		} else {
    			z = deg1 > deg2 ? edge.getFrom() : edge.getTo();
    		}

			
    		double [] pi = new double [n];
    		double tot = 0;
    		for (int k = 0; k < n; k++) {
    			pi [k] = 0;
    			Node y = g.getNode (k);
    			if (k != g.getIndex(z) && g.edgeBetween(z, y) == null) {
    				int dg = 1 + g.degree (y);
    				pi [k] = dg;
    				tot += dg;
    			}
    		}
    		for (int k = 0; k < n; k++) {
    			pi [k] = pi [k] / tot;
    		}
			tot = 0;
    		for (int k = 0; k < n; k++) {
    			double d = pi [k];
    			pi [k] += tot;
    			tot += d;
    		}
    		double r = random.nextDouble ();
    		Node x = null;
    		for (int k = 0; k < n; k++) {
    			if (r < pi [k]) {
    				x = g.getNode (k);
    				break;
    			}
    		}
    		
			//System.err.println ("Connecting " + x + " & " + z);
			Edge.create (x, z, g);
    	}

    	if (g.getAllEdges().size() != sz) throw new GraphException ("Oops! Rewiring delete miscalculated.");
    	return deleteCount;
    }

    public static int rewireWatts (double prob, Graph g, Random random) throws GraphException {
    	int n = g.getNodeCount();
    	if (n < 3) throw new GraphException ("Too few nodes for rewiring");
    	Vector edges = g.getAllEdges();
    	int sz = edges.size();
    	if (sz < 1) throw new GraphException ("Too few edges for rewiring");

    	Vector toDelete = new Vector();
    	int deleteCount = 0;
    	Enumeration enumeration = edges.elements ();
    	while (enumeration.hasMoreElements ()) {
			Edge edge = (Edge) enumeration.nextElement ();
			if (random.nextDouble () < prob) {
				toDelete.addElement (edge);
				deleteCount++;
			}
    	}

		System.err.println ("Deleting a batch of " + (toDelete.size ()) + " edges");
    	enumeration = toDelete.elements ();
    	while (enumeration.hasMoreElements ()) {
			Edge edge = (Edge) enumeration.nextElement ();
			g.deleteEdge (edge);
    	}
    	if (g.getAllEdges().size() != sz-deleteCount) throw new GraphException ("Oops! Rewiring delete failed.");
    	
    	for (int k = 0; k < deleteCount; k++) {
			int i = 0;
			int j = 0;
			Node x = null;
			Node y = null;
			boolean connected = true;
		
			while (connected) {
				//System.err.print (".");
				i = (int) (n * random.nextDouble ());
				x = g.getNode (i);
				j = (int) (n * random.nextDouble ());
				y = g.getNode (j);
				connected = (i == j) || g.edgeBetween(x, y) != null;
			}
			//System.err.println ("Connecting " + x + " & " + y);
			Edge.create (x, y, g);
    	}

    	return deleteCount;
    }

	private static boolean [] neighbourhood (Graph g, int k) {
		int n = g.getNodeCount();
		boolean [] res = new boolean [n];
		for (int i = 0; i < n; i++) {
			res [i] = false;
		}
		Node x = g.getNode (k);
		Enumeration enumeration = g.edgesFrom (x).elements ();
    	while (enumeration.hasMoreElements ()) {
			Edge edge = (Edge) enumeration.nextElement ();
			Node y = edge.getTo ();
			res [g.getIndex (y)] = true;
    	}
    	return res;
	}

	private static double clusterCount (Graph g, boolean [] neigh) {
		int size = 0;
		int count = 0;
		for (int i = 0; i < neigh.length; i++) {
			if (neigh [i]) size++;
		}
		if (size <= 1) return 0;
		Enumeration enumeration = g.getAllEdges ().elements ();
    	while (enumeration.hasMoreElements ()) {
			Edge edge = (Edge) enumeration.nextElement ();
			Node x = edge.getFrom ();
			Node y = edge.getTo ();
			if (neigh [g.getIndex (x)] && neigh[g.getIndex (y)]) count++;
    	}
    	return 2.0 * count / (size * (size - 1.0));
	}

    /** 
    Read a graph from a URL or file.
    @exception java.io.IOException (for I/O or parsing errors)
    */
    public static Graph read (String s) throws GraphException, IOException {
        try {
            URL url = new URL (s);
            return read (url);
        } catch (MalformedURLException ex) {
            File f = new File (s);
            return read (f);
        }
    }

    /** 
    Read a graph from a URL.
    @exception java.io.IOException (for I/O or parsing errors)
    */
    public static Graph read (URL url) throws GraphException, IOException {
        BufferedReader b = new BufferedReader (new InputStreamReader (url.openStream ()));
        return read (b);
    }

    /** 
    Read a graph from a file.
    @exception java.io.IOException (for I/O or parsing errors)
    */
    public static Graph read (File in) throws GraphException, IOException {
        BufferedReader b = new BufferedReader (new FileReader (in));
        return read (b);
    }

    /** 
    Read a graph.
    @exception java.io.IOException (for I/O or parsing errors)
    */
    public static Graph read (BufferedReader in) throws GraphException, IOException {
        Graph g = new Graph ();
        String line = in.readLine ();

        while (line != null) {
            Edge.create (line, g);
            line = in.readLine ();
        }
        in.close ();
        return g;
    }
}