// "Sort" is the class of searching the vertex with largest degree corresponds to 
// covering the largest edge subset with a single vertex.
// In fact, this class is sorting class of given object.
public class Sort {
   public static interface Comparer {
	public int compare(Object a, Object b);
    }
   public static interface Comparable {
	public int compareTo(Object other);
    }
   private static Comparer comparable_comparer = new Comparer() {
	public int compare(Object a, Object b) {
	return ((Comparable)a).compareTo(b);
	}
   };

   public static void st(Comparable[] a)
    {
	st (a, 0, a.length-1, false, comparable_comparer);
    }

   public static void st(Object[] a, Comparer c)
    {
    	st(a, 0, a.length-1 , false, c);
    }

   public static void st(Object[] a, int from, int to, boolean up, Comparer c)
    {
	if ((a == null) || (a.length < 2))
	    return;

	int i = from, j = to;
	Object center = a[(from + to) / 2];
	do {
	    if (up) {
		while ((i < to) && (c.compare(center, a[i]) > 0)) i++;
		while ((j > from) && (c.compare(center, a[j]) < 0)) j--;
	    } else {
		while ((i < to) && (c.compare(center, a[i]) < 0)) i++;	
	while ((j > from) && (c.compare(center, a[j]) > 0)) j--;
	    }

	    if (i < j) {
		Object tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	    }
	    if (i <= j) {i++; j--;};
	} while (i <= j);

	if (from < j) st(a, from, j, up, c); //recursively sort the rest
	if (i < to) st(a, i, to, up, c);
    }
}