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

public class Node implements Comparable {
    private int ID;
    private ArrayList edges;

	static public class Traversal { // Can be either static or dynamic
		int[] level; //level[id] = pathlen from this to id
		double levelAvg;
		int levelMax;
		int levelMed;
		int edges;
		int nodes;
	}

    private Node root;
    private Node parent;
    private int level;
	private Traversal traversal;

    private long searchNum;
	static private long SearchNum = 0;

	static private boolean dbg = false;
	static public void setDbg(boolean debug) {dbg=debug;}

    public static double lop(double d) {
		return lop(d, 2);
    }
    public static double lop(double d, int i) {
		double fact = (double)Math.pow(10, i);
		return Math.round(d*fact)/fact;
    }
    Node(int ID) {
		this.ID = ID;
		edges = new ArrayList();
    }
    public void addEdge(Node node) {
		edges.add(node);
    }
    public void removeEdge(Node node) {
		//	edges.remove(edges.indexOf(node));
		edges.remove(node);
    }
    public int edges() {
		return edges.size();
    }
    public ArrayList edgeList() {
		return edges;
    }
    public int ID() {
		return ID;
    }
    public int compareTo(Object o) { // needed for use in TreeSet
		int id=((Node)o).ID();
		return ID<id?-1:(ID>id?+1:0);
    }
    public int level() {
		return level;
    }
    public int pathLength(int ID) {
		return traversal.level[ID];
    }
    public int pathMax() {
		return traversal.levelMax;
    }
    public double clusterCoeff() {
		int K = edges.size();
		double G = 0.0;
		for (Iterator I=edges.iterator(); I.hasNext();) {
			Node e = (Node)I.next();
			for (Iterator J=e.edges.iterator(); J.hasNext();) {
				Node n = (Node)J.next();
				if (edges.contains(n)) {
					G++;
				}
			}
		}
		G=G/(K*(K-1)); // 2 factored out: double count of edges
		return lop(G);
    }
    public double pathAvg() {
		//return Math.round(traversal.levelAvg*10.0)/10.0;
		return traversal.levelAvg;
    }
    public int pathMed() {
		return traversal.levelMed;
    }
    public int nodeSum() {
		return traversal.nodes;
    }
    public int edgeSum() {
		return traversal.edges;
    }
    public Node root() {
		return root;
    }
    public Node parent() {
		return parent;
    }
    public void resetPath() {
		root=null;
		parent=null;
		level=0;
    }
    public Traversal traverseal() {
		return traversal;
	}
    public Traversal traverse() {
		searchNum = ++SearchNum;
		ArrayList queue = new ArrayList();
		ArrayList list = new ArrayList();
		root = this;
		parent = null;
		level = 0;
		queue.add(this);
		int maxID = 0;		// allow fragmented graphs
		while (queue.size() > 0) {
			Node n = (Node)queue.remove(0);
			maxID = Math.max(maxID,n.ID);
			list.add(n);
			for (Iterator it=n.edges.iterator(); it.hasNext();) {
				Node e = (Node)it.next();
				if (e.searchNum != SearchNum) {
					e.root = this;
					e.searchNum = SearchNum;
					e.parent = n;
					e.level = n.level+1;
					queue.add(e);
				}
			}
		}

		traversal = new Traversal();
		traversal.nodes = list.size();
		//This skips root: size=2=>i=1; last 0 relative index.
		traversal.levelMed = ((Node)list.get(traversal.nodes/2)).level;

		traversal.level = new int[maxID+1];
		Arrays.fill(traversal.level,-1); //-1 => empty (fragmented graph)
		traversal.levelAvg = 0;
		traversal.levelMax = 0;
		traversal.edges = 0;
		for (Iterator it=list.iterator(); it.hasNext();) {
			Node n = (Node)it.next();
			traversal.level[n.ID] = n.level;
			traversal.edges += n.edges();
			traversal.levelAvg += n.level();
			traversal.levelMax = Math.max(n.level(), traversal.levelMax);
		}
		traversal.edges /= 2; //correct double count
		//REMIND: Include root?  This doesnt now. Med also skips root
		traversal.levelAvg /= (double)(traversal.nodes-1);
		traversal.levelAvg = lop(traversal.levelAvg);
		return traversal;
    }
    public long searchNum() {
		return this.searchNum;
    }
	private void DBG (String s) {
		if (dbg)
			System.out.print(s);
	}
    public int searchPowerLaw(int targetID) {
		return searchPowerLaw(targetID, 0);
	}
    public int searchPowerLaw(int targetID, int hops) {
		if (hops==0)
			SearchNum++;
		DBG(ID+" ");
		Node next = this;
		int maxEdges = 0;
		this.searchNum = SearchNum;

		if (this.ID == targetID)
			return hops;
		for (Iterator it=edges.iterator(); it.hasNext();) {
			Node e = (Node)it.next();
			if (e.searchNum != SearchNum) {
				if (e.ID == targetID)
					return hops;
				int edgeSum = 0;
				for (Iterator it1=e.edges.iterator(); it1.hasNext();) {
					Node n = (Node)it1.next(); // n=neighbor
					if (n.searchNum != SearchNum) {
						edgeSum ++;
						if ( n.ID == targetID )
							return hops;
						for (Iterator it2=n.edges.iterator();it2.hasNext();)
							if (((Node)it2.next()).searchNum != SearchNum)
								edgeSum++;
					}
				}
				if (edgeSum > maxEdges) {
					next = e;
					maxEdges = edgeSum;
				}
			}
		}
		hops++;
		if (next == this) {
			DBG("! ");
			return -hops;
		}
		DBG(". ");
		hops = next.searchPowerLaw(targetID, hops);
		if (hops<0)
			return this.searchPowerLaw(targetID,-hops);
		else {
			DBG("\n");
			return hops;
		}
	}
    public int searchDepthFirst(int targetID) {
		return searchDepthFirst(targetID, 0);
	}
    public int searchDepthFirst(int targetID, int hops) {
		if (hops==0)
			SearchNum++;
		DBG(ID+" ");
		Node next = this;
		this.searchNum = SearchNum;

		if (this.ID == targetID)
			return hops;
		ArrayList edgeList = new ArrayList(edges);
		Graph.randShuffle(edgeList);
		for (Iterator it=edgeList.iterator(); it.hasNext();) {
			Node e = (Node)it.next();
			if (e.searchNum != SearchNum) {
				if (e.ID == targetID)
					return hops;
				if(next==this)
					next=e;
				for (Iterator it1=e.edges.iterator(); it1.hasNext();) {
					if ( ((Node)it1.next()).ID == targetID )
						return hops;
				}
			}
		}
		hops++;
		if (next == this) {
			DBG("! ");
			return -hops;
		}
		DBG(". ");
		hops = next.searchDepthFirst(targetID, hops);
		if (hops<0)
			return this.searchDepthFirst(targetID,-hops);
		else {
			DBG("\n");
			return hops;
		}
	}
    public int searchBreadthFirst(int targetID) {
		searchNum = ++SearchNum;
		ArrayList queue = new ArrayList();
		int hops = -1;
		queue.add(this);
		while (queue.size() > 0) {
			hops++;
			Node n = (Node)queue.remove(0);
			if (n.ID == targetID )
				return hops;
			//REMIND: Randomize?
			for (Iterator it=n.edges.iterator(); it.hasNext();) {
				Node e = (Node)it.next();
				if (e.searchNum != SearchNum) {
					e.searchNum = SearchNum;
					queue.add(e);
					if (e.ID == targetID )
						return hops;
					for (Iterator it1=e.edges.iterator(); it1.hasNext();)
						if ( ((Node)it1.next()).ID == targetID )
							return hops;
				}
			}
		}
		return -hops;
	}
    public void print() {
		System.out.print(ID
						 +((root==null)?"":"{"+level+"}")
						 +"["+edges.size()+"]:");
		if (parent != null)
			System.out.print(" "+parent.ID);
		for (Iterator it = edges.iterator(); it.hasNext();) {
			Node e = (Node)it.next();
			if (e != parent)
				System.out.print(" "+e.ID);
		}
		System.out.println();
    }
}