Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out. This time he found an old dusty graph theory notebook with a description of a graph.

It is an undirected weighted graph on n vertices. It is a complete graph: each pair of vertices is connected by an edge. The weight of each edge is either 0 or 1; exactly m edges have weight 1, and all others have weight 0.

Since Ujan doesn't really want to organize his notes, he decided to find the weight of the minimum spanning tree of the graph. (The weight of a spanning tree is the sum of all its edges.) Can you find the answer for Ujan so he stops procrastinating?

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ min((n(n-1))/(2),10^5)), the number of vertices and the number of edges of weight 1 in the graph. 

The i-th of the next m lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), the endpoints of the i-th edge of weight 1.

It is guaranteed that no edge appears twice in the input.

Output

Output a single integer, the weight of the minimum spanning tree of the graph.

Examples

Input


6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6


Output


2


Input


3 0


Output


0

Note

The graph from the first sample is shown below. Dashed edges have weight 0, other edges have weight 1. One of the minimum spanning trees is highlighted in orange and has total weight 2.

<image>

In the second sample, all edges have weight 0 so any spanning tree has total weight 0.
// Hash: 6EWM/JP4lFef3gWLct2BME5ZywmEvvjCFfBt0JrG75o=

import java.security.*;
import java.lang.annotation.*;
import java.nio.file.StandardOpenOption;
import java.util.stream.*;
import java.nio.file.Files;
import java.util.function.*;
import java.util.concurrent.*;
import java.util.*;
import java.nio.file.Paths;
import java.util.concurrent.atomic.AtomicReference;
import java.text.SimpleDateFormat;
import java.nio.charset.*;
import java.nio.file.Path;
import java.io.*;
import java.lang.reflect.*;
import java.text.DecimalFormat;
import java.math.*;



// Solution can be found in Submission.testCase(). psvm method can be found in Main.main(String[] args)
// Please note that the code isn't obfuscated; only compressed


public class Solution {
    public static void main(String[] args) throws Exception {
        Main.main(args);
    }
}


class Main{public static void main(String[]args)throws Exception{Class<?extends AbstractSubmission>clss=TaskD.class;new TaskD().runSubmission();}};







@ContestSubmission(ContestType.CODEFORCES)
@CacheVersion(0)
class TaskD extends AbstractSubmission {

	@Override
	public void testCase() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		UndirectedAdjacencyListGraph graph = new UndirectedAdjacencyListGraph(n);
		for (int i = 0; i < m; i++) {
			graph.addEdge(sc.nextInt()-1, sc.nextInt()-1);
		}

		//debug.println(graph);

		int nax = ThreadLocalRandom.current().nextInt(n);
		int[] ps = IntStream.range(0, n).filter(i -> i != nax).toArray();

		int res = 0;
		Queue<Integer> q = QueueUtils.createFIFO();
		q.add(nax);
		outer: while (ps.length > 0) {
			debug.println();
			debug.println(q);
			int nxt = q.remove();
			debug.println(ps);
			debug.println(nxt);

			HashSet<Integer> set = new HashSet<>();
			for (int i = 0; i < ps.length; i++) {
				debug.println("   " + ps[i] + " " + graph.isEdge(ps[i], nxt));
				if (!graph.isEdge(ps[i], nxt)) {
					set.add(ps[i]);
				}
			}

			if (set.size() == 0) {
				if (q.isEmpty()) {
					res++;
					int nx = ps[ThreadLocalRandom.current().nextInt(ps.length)];
					q.add(nx);
					ps = Arrays.stream(ps).filter(i -> i != nx).toArray();
				}
				continue outer;
			}

			q.addAll(set);
			ps = Arrays.stream(ps).filter(i -> !set.contains(i)).toArray();
		}

		out.println(res);

	}



	@Override
	public void init() {
		// Nothing here! Good for initializing look-up tables or cached values

		// Note that there could be multiple Problem instances running on different threads. Writing static variables
		// here (or anywhere else) could lead to race conditions! Use static initialization instead
	}











	// Set to TRUE to override default (which may both be true or false). Setting to FALSE has no effect

	/* DISABLE-CODE-COMPRESSION: TRUE */
	/* GLOBAL-DISABLE-CODE-COMPRESSION: DEFAULT */
	/* JAVA-6-COMPATIBILITY-MODE: DEFAULT */
	/* KEEP-UNUSED-DEPENDENCIES: DEFAULT */





	
};

abstract class AbstractSubmission{public FastScanner sc;public InputStream in;public PrintStream out;public PrintStream debug;public volatile double score=0;public volatile int testCaseCount=-1;public volatile int testCaseIndex;public volatile double progress=0;public void runSubmission(){runSubmission(false);}public void runSubmission(boolean debug){runSubmission(System.in,System.out,debug);}public void runSubmission(InputStream in,PrintStream out){runSubmission(in,out,false);}public void runSubmission(InputStream in,PrintStream out,boolean debug){runSubmission(in,out,debug?System.err:new VoidPrintStream());}public void runSubmission(InputStream in,OutputStream out,OutputStream debug){this.in=in;this.sc=new FastScanner(this.in);this.out=new PrintStream(out);this.debug=debug instanceof VoidOutputStream||debug instanceof VoidPrintStream?new VoidPrintStream():new DebugPrintStream(debug);ContestType type=getType();testCaseCount=type.testCaseCount;init();if(testCaseCount<=0){testCaseCount=sc.nextInt();sc.nextLine();}testCaseIndex=0;for(testCaseIndex=1;testCaseIndex<=testCaseCount;testCaseIndex++){progress=0;this.out.printf(type.caseString,testCaseIndex,testCaseCount);testCase();}}private class DebugPrintStream extends PrintStream{public DebugPrintStream(OutputStream debug){super(debug);}private Object conv(Object obj){if(obj instanceof byte[])return Arrays.toString((byte[])obj);else if(obj instanceof char[])return Arrays.toString((char[])obj);else if(obj instanceof short[])return Arrays.toString((short[])obj);else if(obj instanceof int[])return Arrays.toString((int[])obj);else if(obj instanceof long[])return Arrays.toString((long[])obj);else if(obj instanceof float[])return Arrays.toString((float[])obj);else if(obj instanceof double[])return Arrays.toString((double[])obj);else if(obj instanceof boolean[])return Arrays.toString((int[])obj);else if(obj instanceof Object[])return Arrays.deepToString((Object[])obj);else return obj;}public void print(Object obj){super.print(conv(obj));}public void println(Object obj){super.println(conv(obj));}}public ContestType getType(){return getType(getClass());}public static ContestType getType(Class<?extends AbstractSubmission>clss){return getAnnotation(clss).value();}private static ContestSubmission getAnnotation(Class<?extends AbstractSubmission>clss){if(!clss.isAnnotationPresent(ContestSubmission.class)){throw new RuntimeException("ContestSubmission annotation not present on class "+clss.getCanonicalName()+"!");}return clss.getAnnotation(ContestSubmission.class);}public abstract void testCase();public abstract void init();};

@Retention(RetentionPolicy.RUNTIME)@Target(ElementType.TYPE)@interface CacheVersion{int value();};

@Retention(RetentionPolicy.RUNTIME)@Target(ElementType.TYPE)@interface ContestSubmission{ContestType value();};

enum ContestType{PLAIN("",-1),ETH_JUDGE("",-1,null,false,false,6),GOOGLE("Case #%d: ",-1),GOOGLE_JAM("Case #%d: ",-1,"Solution.java",false,false,8),GOOGLE_JAM_INTERACTIVE("",-1,"Solution.java",false,false,8),FACEBOOK("Case #%d: ",-1),BLOOMBERG("",1,"Problem.java",false,false,8),SINGLE_TESTCASE("",1),OPTIMIZER("",1,null,false,false,8,true),HACKERRANK("",1,"Solution.java",false,false,8),CODEFORCES("",1,"Solution.java",false,false,8);public int testCaseCount;public String caseString;public String launcher;public boolean disableCompression;public boolean keepUnusedDependencies;public int javaVersion;public boolean isOptimizer;ContestType(String caseString,int testCaseCount,String launcher,boolean disableCompression,boolean keepUnusedDependencies,int javaVersion,boolean isOptimizer){this.caseString=caseString;this.testCaseCount=testCaseCount;this.launcher=launcher;this.disableCompression=disableCompression;this.javaVersion=javaVersion;this.keepUnusedDependencies=keepUnusedDependencies;this.isOptimizer=isOptimizer;}ContestType(String a1,int a2,String a3,boolean a4,boolean a5,int a6){this(a1,a2,a3,a4,a5,a6,false);}ContestType(String a1,int a2){this(a1,a2,null,false,false,8);}};

class FastScanner{private static String spaceDelimiters=" \t\n\r\f";private BufferedReader buffer;private StringTokenizer tokenizer;private InputStream stream;public FastScanner(InputStream stream){this.stream=stream;}public String nextLine(){if(this.buffer==null)this.buffer=new BufferedReader(new InputStreamReader(stream));while(tokenizer==null){try{tokenizer=new StringTokenizer(buffer.readLine()+"\n");}catch(IOException e){throw new RuntimeException("IO exception occured!",e);}}String res=tokenizer.nextToken("");if(!res.endsWith("\n"))throw new RuntimeException("waddaheq just heppenenened");res=res.substring(0,res.length()-1);if(res.contains("\n"))throw new RuntimeException("oke wat lamo");tokenizer=null;return res;}public String next(){if(this.buffer==null)this.buffer=new BufferedReader(new InputStreamReader(stream));while(tokenizer==null||!tokenizer.hasMoreTokens()){try{tokenizer=new StringTokenizer(buffer.readLine()+"\n");}catch(IOException e){throw new RuntimeException("IO exception occured!",e);}}return tokenizer.nextToken(spaceDelimiters);}public BigDecimal nextBigDecimal(){return new BigDecimal(next());}public BigInteger nextBigInteger(){return new BigInteger(next());}public int nextInt(){return Integer.parseInt(next());}public long nextLong(){return Long.parseLong(next());}public double nextDouble(){return Double.parseDouble(next());}};

interface Graph{int getVertexCount();default IntStream vertices(){return IntStream.range(0,getVertexCount());}int getEdgeCount();Iterator<Graph.Edge>edgeIterator();default Set<Graph.Edge>getEdges(){Set<Graph.Edge>result=new HashSet<Graph.Edge>();Iterator<Graph.Edge>iterator=edgeIterator();while(iterator.hasNext())result.add(iterator.next());return Collections.unmodifiableSet(result);}double getEdgeWeight(int v1,int v2);default boolean isEdge(int v1,int v2){return!Double.isNaN(getEdgeWeight(v1,v2));}void setEdgeWeight(int v1,int v2,double weight);default void setEdge(int v1,int v2,boolean edge){if(edge){addEdge(v1,v2);}else{removeEdge(v1,v2);}}default void mapEdgeWeight(int v1,int v2,DoubleUnaryOperator mapper){setEdgeWeight(v1,v2,mapper.applyAsDouble(getEdgeWeight(v1,v2)));}default void mergeEdgeWeight(int v1,int v2,double weight,DoubleBinaryOperator mapper){mapEdgeWeight(v1,v2,w->Double.isNaN(w)?weight:mapper.applyAsDouble(w,weight));}default void addEdge(int v1,int v2){if(!isEdge(v1,v2))setEdgeWeight(v1,v2,1.0);}default void removeEdge(int v1,int v2){setEdgeWeight(v1,v2,Double.NaN);}default void toggleEdge(int v1,int v2){setEdge(v1,v2,!isEdge(v1,v2));}VectorElementIterator getNeighbours(int vertex);default void forEachNeighbour(int vertex,EdgeConsumer action){VectorElementIterator it=getNeighbours(vertex);while(it.hasNext()){action.accept(it.nextInt(),it.getValue());}}@FunctionalInterface interface EdgeConsumer{default void accept(int neighbour){accept(neighbour,1.0);}void accept(int neighbour,double weight);}class Edge extends Structure{public int from;public int to;public double weight;public Edge(int from,int to,double weight){this.from=from;this.to=to;this.weight=weight;}}};

@Retention(RetentionPolicy.SOURCE)@Target(ElementType.METHOD)@interface O{String value();};

@Target(ElementType.FIELD)@Retention(RetentionPolicy.RUNTIME)@interface Optimize{long imin()default 0;long imax()default 100;double fmin()default 0;double fmax()default 1;};

class QueueUtils{public static<T>Queue<T>createFIFO(){return new ArrayDeque<>();}public static<T>Queue<T>createLIFO(){return Collections.asLifoQueue(new ArrayDeque<>());}public static<T>Queue<T>createStack(){return createLIFO();}public static<T extends Comparable<?super T>>Queue<T>createPriority(){return new PriorityQueue<>();}public static<T>Queue<T>createPriority(Comparator<?super T>comparator){return new PriorityQueue<>(comparator);}public static<T,U extends Comparable<?super U>>Queue<T>createPriority(Function<?super T,?extends U>keyExtractor){return createPriority(Comparator.comparing(keyExtractor));}};

abstract class Structure implements Serializable,Cloneable{public Structure clone(){try{Structure struct=(Structure)super.clone();for(Field field:this.getClass().getDeclaredFields()){field.setAccessible(true);if(Modifier.isTransient(field.getModifiers())){continue;}field.set(struct,field.get(this));}return struct;}catch(CloneNotSupportedException e){throw new AssertionError("Cloning a structure should always be supported - please report this bug",e);}catch(IllegalAccessException e){throw new RuntimeException("Can't access my own elements!",e);}}private NavigableMap<String,Object>getFields(){try{NavigableMap<String,Object>result=new TreeMap<String,Object>();for(Field field:this.getClass().getFields()){if(Modifier.isTransient(field.getModifiers())){continue;}result.put(field.getName(),field.get(this));}return result;}catch(IllegalAccessException e){throw new RuntimeException("Can't access my own elements!",e);}}public boolean equals(Object obj){if(obj==null)return false;if(getClass()!=obj.getClass())return false;return getFields().equals(((Structure)obj).getFields());}public int hashCode(){return getFields().hashCode();}public String toString(){return getFields().toString();}};

class Tree<T>implements Serializable{private TreeNode<T>root;Pair<Double,DoubleBinaryOperator>distanceFolder;public Tree(T rootValue){this(rootValue,null);}public Tree(T rootValue,Pair<Double,DoubleBinaryOperator>distanceFolder){this(distanceFolder);initRoot(new TreeNode(rootValue,this));}protected Tree(){this((Pair<Double,DoubleBinaryOperator>)null);}protected Tree(Pair<Double,DoubleBinaryOperator>distanceFolder){this.distanceFolder=distanceFolder==null?new Pair<>(0.0,Double::sum):distanceFolder;}protected void initRoot(TreeNode<T>node){if(root!=null)throw new IllegalStateException("Can't modify the root after it has already been initialized!");this.root=node;}public TreeNode<T>getRoot(){return root;}public String toString(){return root.toString();}};

class Pair<A,B>extends Tuple implements Map.Entry<A,B>{public A a;public B b;public Pair(A a,B b){this.a=a;this.b=b;}public A getLeft(){return a;}public B getRight(){return b;}public void setLeft(A a){this.a=a;}public void setRight(B b){this.b=b;}public<A1,B1>Pair<A1,B1>map(Function<A,A1>mapA,Function<B,B1>mapB){return new Pair<>(mapA.apply(this.a),mapB.apply(this.b));}public A getKey(){return a;}public A setKey(A a){A old=this.a;this.a=a;return old;}public B getValue(){return b;}public B setValue(B b){B old=this.b;this.b=b;return old;}public Object[]toArray(){return new Object[]{a,b};}public boolean equals(Object other){if(!(other instanceof Pair))return super.equals(other);Pair pair=(Pair)other;return Objects.equals(this.a,pair.a)&&Objects.equals(this.b,pair.b);}public int hashCode(){return 961+31*Objects.hashCode(a)+Objects.hashCode(b);}};

class TreeNode<T>implements Serializable{private T value;private int height;private double distance;private double distanceToParent;private List<TreeNode<T>>children;private TreeNode<T>parent;private Tree<T>tree;public TreeNode(T value){this(value,null);}protected TreeNode(T value,Tree<T>tree){this.value=value;this.parent=null;this.tree=tree;this.children=new ArrayList<>(5);this.height=0;this.distance=tree.distanceFolder.a;}protected TreeNode(T value,TreeNode<T>parent,double distanceToParent){this.value=value;this.parent=parent;this.tree=parent.tree;this.children=new ArrayList<>();this.height=parent.getHeight()+1;this.distanceToParent=distanceToParent;this.distance=tree.distanceFolder.b.applyAsDouble(parent.getDistance(),distanceToParent);}public T getValue(){return value;}public void setValue(T value){this.value=value;}public int getHeight(){return height;}public double getDistance(){return distance;}public double getDistanceToParent(){if(!hasParent())throw new NoSuchElementException("Node has no parent!");return this.distanceToParent;}public List<TreeNode<T>>getChildren(){return this.children.size()==0?Collections.emptyList():Collections.unmodifiableList(children);}public int getChildCount(){return children.size();}public TreeNode<T>addChild(T value){return addChild(value,1);}public TreeNode<T>addChild(T value,double distance){return createUnattached(value,distance).attach();}public TreeNode<T>.Unattached createUnattached(T value,double distance){return new Unattached(value,distance);}class Unattached extends TreeNode<T>{private boolean isAttached=false;private Unattached(T value,double distance){super(value,TreeNode.this,distance);}public TreeNode<T>attach(){if(isAttached())throw new NoSuchElementException("Node has already been attached!");TreeNode.this.children.add(this);isAttached=true;return this;}public boolean isAttached(){return isAttached;}}public TreeNode<T>getParent(){return parent;}public List<TreeNode<T>>getParentChain(){List<TreeNode<T>>res=new ArrayList<>();TreeNode<T>node=this;while((node=node.getParent())!=null){res.add(node);}Collections.reverse(res);return res;}public boolean hasParent(){return getParent()!=null;}public Tree<T>getTree(){return tree;}public boolean isAttached(){return true;}public String toString(){return value.toString()+(children.isEmpty()?"":children.toString());}};

abstract class Tuple extends Structure{public abstract Object[]toArray();public boolean equals(Object obj){if(obj==null)return false;if(!(obj instanceof Tuple))return false;return Arrays.equals(this.toArray(),((Tuple)obj).toArray());}public int hashCode(){return Arrays.hashCode(this.toArray());}public String toString(){Object[]els=toArray();String[]elements=new String[els.length];for(int i=0;i<els.length;i++){elements[i]=""+els[i];}return "("+String.join(", ",elements)+")";}};

class UndirectedAdjacencyListGraph extends UndirectedMatrixGraph{public UndirectedAdjacencyListGraph(int vertices){super(new RowListSparseMatrix(vertices,vertices,Double.NaN));}public UndirectedAdjacencyListGraph(Matrix matrix){super(new RowListSparseMatrix(matrix,Double.NaN));}public UndirectedAdjacencyListGraph(Graph graph){this(graph.getVertexCount());for(Iterator<Edge>iterator=graph.edgeIterator();iterator.hasNext();){Edge next=iterator.next();this.setEdgeWeight(next.from,next.to,next.weight);}}};

interface Matrix extends Iterable<Triple<Integer,Integer,Double>>{double get(int row,int column);double set(int row,int column,double value);default void setAll(double value){apply(a->value);}default void apply(Function<Double,Double>func){int n=this.getRowCount();int m=this.getColumnCount();for(int a=0;a<n;a++){for(int b=0;b<m;b++){this.set(a,b,func.apply(this.get(a,b)));}}}int getRowCount();int getColumnCount();default int getElementCount(){return getRowCount()*getColumnCount();}default boolean isSquare(){return getRowCount()==getColumnCount();}default VectorElementIterator getRowElements(int row){return getFilteredRowElements(row,null);}default VectorElementIterator getFilteredRowElements(int row,DoublePredicate filter){if(row<0||row>=getRowCount())throw new IllegalArgumentException();Matrix outer=this;return new VectorElementIterator(){private double value;private int cur=-1;private boolean isValid=false;public double getValue(){if(cur<0)throw new NoSuchElementException();return value;}public double setValue(double value){if(cur<0)throw new NoSuchElementException();this.value=value;return outer.set(row,cur,value);}public boolean hasNext(){while(!isValid){if(++cur>=getColumnCount())return false;value=outer.get(row,cur);isValid=filter==null||filter.test(value);}return true;}public int nextInt(){if(!hasNext())throw new NoSuchElementException();isValid=false;return cur;}};}default VectorElementIterator getColumnElements(int column){return getFilteredColumnElements(column,null);}default VectorElementIterator getFilteredColumnElements(int column,DoublePredicate filter){if(column<0||column>=getColumnCount())throw new IllegalArgumentException();Matrix outer=this;return new VectorElementIterator(){private double value;private int cur=-1;private boolean isValid=false;public double getValue(){if(cur<0)throw new NoSuchElementException();return value;}public double setValue(double value){if(cur<0)throw new NoSuchElementException();this.value=value;return outer.set(cur,column,value);}public boolean hasNext(){while(!isValid){if(++cur>=getColumnCount())return false;value=outer.get(cur,column);isValid=filter==null||filter.test(value);}return true;}public int nextInt(){if(!hasNext())throw new NoSuchElementException();isValid=false;return cur;}};}default VectorElementIterator getRowNonZeroes(int row){return getRowNonValued(row,0);}default VectorElementIterator getRowNonValued(int row,double value){return getFilteredRowElements(row,a->!MathUtils.doubleEquals(a,value));}default VectorElementIterator getColumnNonZeroes(int column){return getColumnNonValued(column,0);}default VectorElementIterator getColumnNonValued(int column,double value){return getFilteredColumnElements(column,a->!MathUtils.doubleEquals(a,value));}default Matrix transposeView(){return new TransposeMatrix(this);}default boolean isSparse(){return false;}default Iterator<Triple<Integer,Integer,Double>>iterator(){return new Iterator<Triple<Integer,Integer,Double>>(){private int i=0;private double result;public boolean hasNext(){while(i<getElementCount()){double r=get(i%getRowCount(),i/getRowCount());if(r!=0){result=r;return true;}i++;}return false;}public Triple<Integer,Integer,Double>next(){if(!hasNext())throw new NoSuchElementException();Triple<Integer,Integer,Double>t=new Triple<>(i%getRowCount(),i/getRowCount(),result);i++;return t;}};}static<T extends Matrix>T combine(Matrix a,Matrix b,Supplier<T>matrixSupplier,BiFunction<Double,Double,Double>combiner){if(a.getRowCount()!=b.getRowCount()||a.getColumnCount()!=b.getColumnCount())throw new IllegalArgumentException("Matrices must have the same dimensions!");T result=matrixSupplier.get();boolean isDense=!(a instanceof SparseMatrix&&b instanceof SparseMatrix);if(isDense){for(int i=0;i<result.getRowCount();i++){for(int j=0;j<result.getColumnCount();j++){result.set(i,j,combiner.apply(a.get(i,j),b.get(i,j)));}}}else{for(int i=0;i<result.getRowCount();i++){for(int j=0;j<result.getColumnCount();j++){result.set(i,j,combiner.apply(a.get(i,j),b.get(i,j)));}}}return result;}};

class MathUtils{private MathUtils(){}public static int[]splitIntoArray(int i,int[]max){int[]res=new int[max.length];for(int j=max.length-1;j>=0;j--){res[j]=i%max[j];i/=max[j];}return res;}public static int mergeIntoInteger(int[]arr,int[]max){int result=0;for(int i=0;i<max.length;i++){result*=max[i];result+=arr[i];}return result;}public static int foldl(IntBinaryOperator operator,int...vals){int result=vals[0];for(int i=1;i<vals.length;i++){result=operator.applyAsInt(result,vals[i]);}return result;}public static int min(int a,int b){return Math.min(a,b);}public static int max(int a,int b){return Math.max(a,b);}public static int min(int a,int b,int c){return Math.min(a,Math.min(b,c));}public static int max(int a,int b,int c){return Math.max(a,Math.max(b,c));}public static int min(int...vals){return foldl(Math::min,vals);}public static int max(int...vals){return foldl(Math::max,vals);}public static int sum(int...vals){int result=0;for(int v:vals){result+=v;}return result;}public static int prod(int...vals){int result=1;for(int v:vals){result*=v;}return result;}public static int factorial(int n){if(n<=1)return 1;return n*factorial(n-1);}public static boolean doubleEquals(double a,double b){return a==b||(Double.isNaN(a)&&Double.isNaN(b));}public static int pow(int a,int exponent){if(exponent<0)return 0;if(exponent==0)return 1;if((a&(a-1))==0)return a<<(exponent-1);if(exponent%2==0)return sq(pow(a,exponent/2));return pow(a,exponent-1)*a;}public static long pow(long a,long exponent){if(a==2)return 1l<<exponent;if(exponent<0)return 0;if(exponent==0)return 1;if(exponent%2==0)return sq(pow(a,exponent/2));return pow(a,exponent-1)*a;}public static double pow(double a,double exponent){return Math.pow(a,exponent);}public static int sq(int a){return a*a;}public static long sq(long a){return a*a;}public static double sq(double a){return a*a;}public static int realMod(int i,int mod){return MathUtils.floorMod(i,mod);}public static long realMod(long i,long mod){return MathUtils.floorMod(i,mod);}public static int floorDiv(int a,int b){return Math.floorDiv(a,b);}public static long floorDiv(long a,long b){return Math.floorDiv(a,b);}public static int floorMod(int a,int b){return Math.floorMod(a,b);}public static long floorMod(long a,long b){return Math.floorMod(a,b);}public static int ceilDiv(int a,int b){return Math.floorDiv(a+b-1,b);}public static long ceilDiv(long a,long b){return Math.floorDiv(a+b-1,b);}public static int ceilMod(int a,int b){return a-ceilDiv(a,b)*b;}public static long ceilMod(long a,long b){return a-ceilDiv(a,b)*b;}public static long modMul(long a,long b,long mod){a=realMod(a,mod);if(a==0)return 0;b=realMod(b,mod);if(b<=Long.MAX_VALUE/a){return MathUtils.realMod(a*b,mod);}return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValueExact();}public static long modAdd(long a,long b,long mod){a=realMod(a,mod);b=realMod(b,mod);return realMod(a-mod+b,mod);}};

abstract class MatrixGraph extends AbstractGraph implements Graph{private ResizableMatrix matrix;private IntArrayList inDegrees;private IntArrayList outDegrees;private int edges=0;private boolean directed;MatrixGraph(boolean directed,ResizableMatrix matrix){if(!matrix.isSquare())throw new IllegalArgumentException("Matrix must be square!");this.directed=directed;this.matrix=matrix;this.inDegrees=IntArrayList.ofSize(getVertexCount());if(this.directed){this.outDegrees=IntArrayList.ofSize(getVertexCount());}else{this.outDegrees=null;}this.matrix.setAll(Double.NaN);}public ResizableMatrix getMatrix(){return matrix;}public int getVertexCount(){return matrix.getRowCount();}public int getEdgeCount(){return edges;}public Iterator<Graph.Edge>edgeIterator(){return new Iterator<Edge>(){private int vertex=-1;private VectorElementIterator iterator=null;private Edge nxt=null;public boolean hasNext(){int n=getVertexCount();if(nxt==null){do{while(iterator==null||!iterator.hasNext()){if(++vertex>=n)return false;iterator=getNeighbours(vertex);}nxt=new Edge(vertex,iterator.nextInt(),iterator.getValue());}while(!directed&&nxt.to>=nxt.from);}return true;}public Edge next(){if(!hasNext())throw new NoSuchElementException();Edge res=nxt;nxt=null;return res;}};}public double getEdgeWeight(int v1,int v2){rangeChecks(v1,v2);return matrix.get(v1,v2);}public void setEdgeWeight(int v1,int v2,double weight){rangeChecks(v1,v2);double d=weight;int weightZ=Double.isNaN(d)?0:1;int prevWeightZ=Double.isNaN(this.matrix.set(v1,v2,d))?0:1;int change=weightZ-prevWeightZ;edges+=change;if(!directed){this.matrix.set(v2,v1,d);}inDegrees.set(v2,inDegrees.get(v2)+change);if(directed){outDegrees.set(v1,outDegrees.get(v1)+change);}else{inDegrees.set(v1,inDegrees.get(v1)+change);}}public VectorElementIterator getNeighbours(int vertex){return this.matrix.getRowNonValued(vertex,Double.NaN);}int getInDegree(int vertex){return inDegrees.get(vertex);}int getOutDegree(int vertex){return outDegrees.get(vertex);}};

abstract class AbstractGraph implements Graph,Serializable{public boolean equals(Object other){if(other==null)return false;if(!(other instanceof Graph))return false;Graph graph=(Graph)other;if(this.getVertexCount()!=graph.getVertexCount())return false;if(this.getEdgeCount()!=graph.getEdgeCount())return false;for(Iterator<Graph.Edge>iterator=this.edgeIterator();iterator.hasNext();){Graph.Edge next=iterator.next();int v1=next.from,v2=next.to;if(this.getEdgeWeight(v1,v2)!=graph.getEdgeWeight(v1,v2))return false;}return true;}public int hashCode(){return Objects.hash(this.getVertexCount(),this.getEdgeCount(),Utils.hashAll(this.edgeIterator()));}public String toString(){StringBuilder result=new StringBuilder();for(int i=0;i<getVertexCount();i++){if(i!=0)result.append("\n");for(int j=0;j<getVertexCount();j++){if(j!=0)result.append(", ");result.append(this.getEdgeWeight(i,j));}}return result.toString();}protected void rangeChecks(int v1,int v2)throws IllegalArgumentException{int V=getVertexCount();if(v1<0||v2<0||v1>=V||v2>=V)throw new IllegalArgumentException();}};

class IntArrayList implements Serializable{private int[]arr;private int length=0;public IntArrayList(){this(10);}public IntArrayList(int initialCapacity){this.arr=new int[initialCapacity];}public IntArrayList(int[]array){this.arr=Arrays.copyOf(array,array.length);}public IntArrayList(List<Integer>list){this.arr=new int[list.size()];for(int i=0;i<list.size();i++){arr[i]=list.get(i);}}public static IntArrayList ofSize(int size){IntArrayList result=new IntArrayList(size);result.length=size;return result;}public static IntArrayList ofSize(int size,int element){IntArrayList result=new IntArrayList(size);result.length=size;for(int i=0;i<element;i++){result.arr[i]=element;}return result;}public int[]toArray(){return Arrays.copyOf(arr,length);}public int size(){return length;}public int get(int index){return arr[index];}public int set(int index,int val){int prev=arr[index];arr[index]=val;return prev;}public void add(int val){ensureCapacity(length+1);arr[length]=val;length++;}public void add(int index,int val){rangeCheckAdd(index);shift(index,1);arr[index]=val;}public void addAll(int[]val){addAll(length,val);}public void addAll(int index,int[]val){rangeCheckAdd(index);shift(index,val.length);for(int i=0;i<val.length;i++){arr[index+i]=val[i];}}public int remove(int index){int prev=arr[index];shift(index+1,-1);return prev;}public void removeAll(Range range){rangeCheck(range.a);rangeCheck(range.b);range.ensureValidity();shift(range.b,range.a-range.b);}public void clear(){shift(length,-length);}private void shift(int startIndex,int shift){ensureCapacity(length+shift);if(shift>0){for(int i=length-1;i>=startIndex;i--){arr[i+shift]=arr[i];}}else if(shift<0){for(int i=startIndex;i<length;i++){arr[i+shift]=arr[i];}}length+=shift;}private void rangeCheck(int index){if(index<0||index>=length)throw new IllegalArgumentException("Index out of range: "+index);}private void rangeCheckAdd(int index){if(index<0||index>length)throw new IllegalArgumentException("Index out of range: "+index);}private void ensureCapacity(int minCapacity){if(arr.length>=minCapacity)return;int newCapacity=minCapacity+length;if(newCapacity<0)newCapacity=Integer.MAX_VALUE;arr=Arrays.copyOf(arr,newCapacity);}};

class Range extends Pair<Integer,Integer>implements Iterable<Integer>{public Range(int i,int j){super(i,j);}public Range(Range range){this(range.a,range.b);}public int size(){return this.b-this.a;}public int[]toIntArray(){return this.stream().toArray();}public LongRange toLongRange(){return new LongRange(this.a,this.b);}public IntStream stream(){return IntStream.range(a,b);}public Iterator<Integer>iterator(){return new PolyfillIterator<Integer>(){int c=getLeft();public boolean hasNext(){return c<getRight();}public Integer next(){return c++;}};}public boolean contains(int l){return l>=this.a&&l<this.b;}public void intersectWith(Range range){a=Math.max(range.a,a);b=Math.min(range.b,b);}public Range intersectedWith(Range range){Range res=new Range(this);res.intersectWith(range);return res;}public static Range getIntersection(Range...a){return Arrays.stream(a).reduce((res,b)->res.intersectedWith(b)).get();}public void ensureValidity()throws IllegalArgumentException{if(this.b<this.a)throw new IllegalArgumentException("Second argument of range ("+this.a+", "+this.b+") must be larger than first");}};

class LongRange extends Pair<Long,Long>implements Iterable<Long>{public LongRange(long i,long j){super(i,j);}public LongRange(LongRange range){this(range.a,range.b);}public long size(){return this.b-this.a;}public long[]toLongArray(){return this.stream().toArray();}public Range toIntRange(){return new Range((int)(long)this.a,(int)(long)this.b);}public LongStream stream(){return LongStream.range(a,b);}public Iterator<Long>iterator(){return new PolyfillIterator<Long>(){long c=getLeft();public boolean hasNext(){return c<getRight();}public Long next(){return c++;}};}public boolean contains(long l){return l>=this.a&&l<this.b;}public void intersectWith(LongRange range){a=Math.max(range.a,a);b=Math.min(range.b,b);}public LongRange intersectedWith(LongRange range){LongRange res=new LongRange(this);res.intersectWith(range);return res;}public static LongRange getIntersection(LongRange...a){return Arrays.stream(a).reduce((res,b)->res.intersectedWith(b)).get();}public void ensureValidity()throws IllegalArgumentException{if(this.b<this.a)throw new IllegalArgumentException("Second argument of range ("+this.a+", "+this.b+") must be larger than first");}};

abstract class PolyfillIterator<T>implements Iterator<T>{};

interface ResizableMatrix extends Matrix{void addRow(int index);default void addRow(){addRow(this.getRowCount());}void removeRow(int index);void addColumn(int index);default void addColumn(){addRow(this.getColumnCount());}void removeColumn(int index);default ResizableMatrix transposeView(){return new TransposeMatrix.Resizable(this);}};

class RowListSparseMatrix extends AbstractMatrix implements ResizableMatrix,SparseMatrix{private int clmnsCount;private double sparseValue;private ArrayList<SparseVector>rows;private SparseVector emptyRow;public RowListSparseMatrix(){this(0,0);}public RowListSparseMatrix(int initialRows,int initialColumns){this(initialRows,initialColumns,0);}public RowListSparseMatrix(int initialRows,int initialColumns,double sparseValue){this.sparseValue=sparseValue;this.rows=new ArrayList<>(Math.max(initialRows,10));this.clmnsCount=initialColumns;emptyRow=SparseVector.empty(clmnsCount,getSparseValue());for(int i=0;i<initialRows;i++){addRow();}}public RowListSparseMatrix(Matrix fromMatrix,double sparseValue){this(fromMatrix.getRowCount(),fromMatrix.getColumnCount(),sparseValue);AbstractMatrix.copyAllNon(fromMatrix,this,sparseValue);}public void setAll(double value){if(isSparseValue(value)){clear();}else{super.setAll(value);}}public double get(int row,int column){rangeChecks(row,column);return rows.get(row).get(column);}private SparseVector getRowModifiable(int index){SparseVector result=rows.get(index);if(result!=emptyRow){return result;}else{result=new SparseVector(clmnsCount,getSparseValue());rows.set(index,result);return result;}}public double set(int row,int column,double value){rangeChecks(row,column);return getRowModifiable(row).set(column,value);}public int getRowCount(){return rows.size();}public int getColumnCount(){return clmnsCount;}public void addRow(int index){if(index<0||index>getRowCount())throw new IllegalArgumentException();rows.add(index,emptyRow);}public void removeRow(int index){if(index<0||index>=getRowCount())throw new IllegalArgumentException();rows.remove(index);}public void addColumn(int index){if(index<0||index>getColumnCount())throw new IllegalArgumentException();clmnsCount++;if(index==clmnsCount-1)return;for(SparseVector vec:rows){vec.add(index,getSparseValue());}}public void removeColumn(int index){if(index<0||index>=getColumnCount())throw new IllegalArgumentException();clmnsCount--;for(SparseVector vec:rows){vec.remove(index);}}public VectorElementIterator getRowNonValued(int row,double value){if(!isSparseValue(value))return super.getRowNonValued(row,value);if(row<0||row>=getRowCount())throw new IllegalArgumentException();return rows.get(row).iterator();}public Iterator<Triple<Integer,Integer,Double>>iterator(){return new PolyfillIterator<Triple<Integer,Integer,Double>>(){int rowi=-1;VectorElementIterator colit;public boolean hasNext(){while(colit==null||!colit.hasNext()){if(++rowi>=getRowCount())return false;colit=rows.get(rowi).iterator();}return true;}public Triple<Integer,Integer,Double>next(){if(!hasNext())throw new NoSuchElementException();int c=colit.nextInt();return new Triple<>(rowi,c,colit.getValue());}};}public double getSparseValue(){return sparseValue;}public void clear(){for(SparseVector row:rows){if(row==emptyRow)continue;row.clear();}}};

abstract class AbstractMatrix implements Matrix,Serializable{public String toString(){StringBuilder result=new StringBuilder();for(int i=0;i<getRowCount();i++){if(i!=0)result.append("\n");for(int j=0;j<getColumnCount();j++){if(j!=0)result.append(", ");result.append(this.get(i,j));}}return result.toString();}public boolean equals(Object obj){if(obj==null)return false;if(!(obj instanceof Matrix))return false;Matrix other=(Matrix)obj;if(this.getColumnCount()!=other.getColumnCount())return false;if(this.getRowCount()!=other.getRowCount())return false;Matrix o1=this;Matrix o2=other;if(o2 instanceof SparseMatrix){Matrix o3=o1;o1=o2;o2=o3;}for(int it=0;it<2;it++){if(o1 instanceof DenseMatrix){for(int i=0;i<o1.getRowCount();i++){for(int j=0;j<o1.getColumnCount();j++){if(o1.get(i,j)!=o2.get(i,j))return false;}}return true;}for(Triple<Integer,Integer,Double>next:o1){if(o2.get(next.a,next.b)!=next.c)return false;}Matrix o3=o1;o1=o2;o2=o3;}return true;}public int hashCode(){return Objects.hash(Utils.hashAll(this.iterator()),this.getRowCount(),this.getColumnCount());}protected static void copyAllNon(Matrix from,Matrix to,double value){if(from.getRowCount()>to.getRowCount()||from.getColumnCount()>to.getColumnCount())throw new IllegalArgumentException("from matrix too large");if(from instanceof SparseMatrix&&MathUtils.doubleEquals(((SparseMatrix)from).getSparseValue(),value)){for(Triple<Integer,Integer,Double>t:from){to.set(t.getLeft(),t.getMiddle(),t.getRight());}}else{for(int i=0;i<from.getRowCount();i++){for(int j=0;j<from.getColumnCount();j++){double g=from.get(i,j);if(!MathUtils.doubleEquals(value,g))to.set(i,j,g);}}}}protected void rangeChecks(int row,int column){if(row<0||column<0||row>=getRowCount()||column>=getColumnCount())throw new IllegalArgumentException();}};

interface DenseMatrix extends Matrix{};

interface SparseMatrix extends Matrix{double getSparseValue();default boolean isSparseValue(double d){return MathUtils.doubleEquals(d,getSparseValue());}void clear();default boolean isSparse(){return true;}};

class SparseVector implements Serializable{private static int useHashMapAt=64;private IntArrayList inds;private DoubleArrayList values;private Map<Integer,Double>map;int length;private double sparseValue;public SparseVector(int length,double sparseValue){this.sparseValue=sparseValue;this.length=length;clear();}public void clear(){inds=new IntArrayList(4);values=new DoubleArrayList(4);map=null;}private void switchToMap(){map=new HashMap<>(2*useHashMapAt);for(int i=0;i<inds.size();i++){map.put(inds.get(i),values.get(i));}inds=null;values=null;}public int size(){return length;}public double get(int index){rangeCheck(index);if(map==null){for(int i=0;i<inds.size();i++){if(inds.get(i)==index)return values.get(i);}}else{Double d=map.get(index);if(d!=null)return d;}return getSparseValue();}public double set(int index,double value){rangeCheck(index);boolean isSparse=isSparseValue(value);if(map==null){int size=inds.size();for(int i=0;i<size;i++){if(inds.get(i)==index){if(!isSparse){return values.set(i,value);}else{inds.set(i,inds.get(size-1));double res=values.set(i,values.get(size-1));values.remove(size-1);inds.remove(size-1);return res;}}}if(isSparse)return value;if(size+1>=useHashMapAt)switchToMap();if(map==null){inds.add(index);values.add(value);return getSparseValue();}}Double d=isSparse?map.remove(index):map.put(index,value);if(d==null){return getSparseValue();}else{return d;}}public void add(int index,double value){rangeCheckAdd(index);shift(index,1);set(index,value);}public double remove(int index){rangeCheck(index);double res=get(index);shift(index,-1);return res;}private void shift(int index,int by){if(map==null){int size=inds.size();for(int i=0;i<size;i++){int g=inds.get(i);if(g>=index){inds.set(i,g+by);}}}else{Map<Integer,Double>n=new HashMap<>(map.size());Iterator<Map.Entry<Integer,Double>>iterator=map.entrySet().iterator();while(iterator.hasNext()){Map.Entry<Integer,Double>entry=iterator.next();if(entry.getKey()>=index){iterator.remove();n.put(entry.getKey()+by,entry.getValue());}}map.putAll(n);}length+=by;}public double getSparseValue(){return sparseValue;}public boolean isSparseValue(double d){return MathUtils.doubleEquals(d,getSparseValue());}private void rangeCheck(int index){if(index<0||index>=length)throw new IllegalArgumentException("Index out of range: "+index);}private void rangeCheckAdd(int index){if(index<0||index>length)throw new IllegalArgumentException("Index out of range: "+index);}public VectorElementIterator iterator(){if(map==null){return new VectorElementIterator(){int cur=0;public double getValue(){return values.get(cur-1);}public double setValue(double value){return values.set(cur-1,value);}public boolean hasNext(){return cur<inds.size();}public int nextInt(){if(!hasNext())throw new NoSuchElementException();return inds.get(cur++);}};}else{return new VectorElementIterator(){Map.Entry<Integer,Double>cur=null;Iterator<Map.Entry<Integer,Double>>iterator=SparseVector.this.map.entrySet().iterator();public double getValue(){return cur.getValue();}public double setValue(double value){return cur.setValue(value);}public boolean hasNext(){return iterator.hasNext();}public int nextInt(){return(cur=iterator.next()).getKey();}};}}public static SparseVector empty(int length,double sparseValue){return new SparseVector(length,sparseValue){public double get(int index){return getSparseValue();}public void add(int index,double value){this.length++;}public double remove(int index){this.length--;return getSparseValue();}public double set(int index,double value){throw new UnsupportedOperationException();}};}};

class DoubleArrayList implements Serializable{private double[]arr;private int length=0;public DoubleArrayList(){this(10);}public DoubleArrayList(int initialCapacity){this.arr=new double[initialCapacity];}public DoubleArrayList(double[]array){this.arr=Arrays.copyOf(array,array.length);}public DoubleArrayList(List<Double>list){this.arr=new double[list.size()];for(int i=0;i<list.size();i++){arr[i]=list.get(i);}}public static DoubleArrayList ofSize(int size){DoubleArrayList result=new DoubleArrayList(size);result.length=size;return result;}public static DoubleArrayList ofSize(int size,double element){DoubleArrayList result=new DoubleArrayList(size);result.length=size;for(int i=0;i<element;i++){result.arr[i]=element;}return result;}public double[]toArray(){return Arrays.copyOf(arr,length);}public int size(){return length;}public double get(int index){return arr[index];}public double set(int index,double val){double prev=arr[index];arr[index]=val;return prev;}public void add(double val){ensureCapacity(length+1);arr[length]=val;length++;}public void add(int index,double val){rangeCheckAdd(index);shift(index,1);arr[index]=val;}public void addAll(double[]val){addAll(length,val);}public void addAll(int index,double[]val){rangeCheckAdd(index);shift(index,val.length);for(int i=0;i<val.length;i++){arr[index+i]=val[i];}}public double remove(int index){rangeCheck(index);double prev=arr[index];shift(index+1,-1);return prev;}public void removeAll(Range range){rangeCheck(range.a);rangeCheck(range.b);range.ensureValidity();shift(range.b,range.a-range.b);}public void clear(){shift(length,-length);}private void shift(int startIndex,int shift){ensureCapacity(length+shift);if(shift>0){for(int i=length-1;i>=startIndex;i--){arr[i+shift]=arr[i];}}else if(shift<0){for(int i=startIndex;i<length;i++){arr[i+shift]=arr[i];}}length+=shift;}private void rangeCheck(int index){if(index<0||index>=length)throw new IllegalArgumentException("Index out of range: "+index);}private void rangeCheckAdd(int index){if(index<0||index>length)throw new IllegalArgumentException("Index out of range: "+index);}private void ensureCapacity(int minCapacity){if(arr.length>=minCapacity)return;int newCapacity=minCapacity+length;if(newCapacity<0)newCapacity=Integer.MAX_VALUE;arr=Arrays.copyOf(arr,newCapacity);}};

class TransposeMatrix extends AbstractMatrix{private Matrix matrix;public TransposeMatrix(Matrix original){matrix=original;}public static class Resizable extends TransposeMatrix implements ResizableMatrix{private ResizableMatrix resizable;public Resizable(ResizableMatrix original){super(original);this.resizable=original;}public void addRow(int index){resizable.addColumn(index);}public void removeRow(int index){resizable.removeColumn(index);}public void addColumn(int index){resizable.addRow(index);}public void removeColumn(int index){resizable.removeRow(index);}public ResizableMatrix transposeView(){return resizable;}}public double get(int row,int column){return matrix.get(column,row);}public double set(int row,int column,double value){return matrix.set(column,row,value);}public void setAll(double value){matrix.setAll(value);}public int getRowCount(){return matrix.getColumnCount();}public int getColumnCount(){return matrix.getRowCount();}public int getElementCount(){return matrix.getElementCount();}public boolean isSquare(){return matrix.isSquare();}public VectorElementIterator getRowElements(int row){return matrix.getColumnElements(row);}public VectorElementIterator getFilteredRowElements(int row,DoublePredicate filter){return matrix.getFilteredColumnElements(row,filter);}public VectorElementIterator getColumnElements(int column){return matrix.getRowElements(column);}public VectorElementIterator getFilteredColumnElements(int column,DoublePredicate filter){return matrix.getFilteredRowElements(column,filter);}public VectorElementIterator getRowNonZeroes(int row){return matrix.getColumnNonZeroes(row);}public VectorElementIterator getRowNonValued(int row,double value){return matrix.getColumnNonValued(row,value);}public VectorElementIterator getColumnNonZeroes(int column){return matrix.getRowNonZeroes(column);}public VectorElementIterator getColumnNonValued(int column,double value){return matrix.getRowNonValued(column,value);}public Matrix transposeView(){return matrix;}public boolean isSparse(){return matrix.isSparse();}public Iterator<Triple<Integer,Integer,Double>>iterator(){return matrix.iterator();}};

class Triple<A,B,C>extends Tuple{public A a;public B b;public C c;public Triple(A a,B b,C c){this.a=a;this.b=b;this.c=c;}public A getLeft(){return a;}public B getMiddle(){return b;}public C getRight(){return c;}public void setLeft(A a){this.a=a;}public void setMiddle(B b){this.b=b;}public void setRight(C c){this.c=c;}public<A1,B1,C1>Triple<A1,B1,C1>map(Function<A,A1>mapA,Function<B,B1>mapB,Function<C,C1>mapC){return new Triple<>(mapA.apply(this.a),mapB.apply(this.b),mapC.apply(this.c));}public Object[]toArray(){return new Object[]{a,b,c};}};

abstract class UndirectedMatrixGraph extends MatrixGraph implements UndirectedGraph{public UndirectedMatrixGraph(ResizableMatrix matrix){super(false,matrix);}public int getDegree(int vertex){return getInDegree(vertex);}};

interface UndirectedGraph extends Graph{int getDegree(int vertex);};

class Utils{private Utils(){}public static void repeat(int times,Consumer<Integer>consumer){for(int i=0;i<times;i++){consumer.accept(i);}}public static void repeat(int times,Runnable runnable){repeat(times,(a)->runnable.run());}public static<E extends Throwable>double timing(ThrowingRunnable<E>runnable)throws E{long start=System.nanoTime();runnable.run();long end=System.nanoTime();return(end-start)/1_000_000_000.0;}private static int timingId=0;public static<T,E extends Throwable>T printTiming(ThrowingSupplier<T,E>supplier,String name)throws E{int tid=timingId++;if(name==null)name=""+tid;else name=tid+" - "+name;System.err.println("Starting task "+name);long start=System.nanoTime();try{return supplier.get();}finally{long end=System.nanoTime();System.err.println("Time taken for task "+name+": "+(end-start)/1_000_000_000.0+"s");}}public static<E extends Throwable>void printTiming(ThrowingRunnable<E>runnable,String name)throws E{printTiming(()->{runnable.run();return null;},name);}public static<E extends Throwable>void printTiming(ThrowingRunnable<E>runnable)throws E{printTiming(runnable,null);}public static<T,E extends Throwable>T printTiming(ThrowingSupplier<T,E>supplier)throws E{return printTiming(supplier,null);}public static<T>ArrayList<T>toArrayList(Iterable<T>iterable){int size=iterable instanceof Collection?((Collection)iterable).size():-1;return toArrayList(iterable,size);}public static<T>ArrayList<T>toArrayList(Iterable<T>iterable,int size){return toArrayList(iterable.iterator(),size);}public static<T>ArrayList<T>toArrayList(Iterator<T>iterator){return toArrayList(iterator,-1);}public static<T>ArrayList<T>toArrayList(Iterator<T>iterator,int estimatedSize){return toArrayList(Spliterators.spliterator(iterator,estimatedSize,Spliterator.ORDERED));}public static<T>ArrayList<T>toArrayList(Spliterator<T>spliterator){long estimatedSize=spliterator.estimateSize();if(estimatedSize>=Long.MAX_VALUE||estimatedSize<=10)estimatedSize=10;ArrayList<T>result=new ArrayList<>((int)Math.min(estimatedSize,Integer.MAX_VALUE));spliterator.forEachRemaining(result::add);return result;}public static IntStream stream(PrimitiveIterator.OfInt iterator){return stream(iterator,-1);}public static IntStream stream(PrimitiveIterator.OfInt iterator,int estimatedSize){return stream(Spliterators.spliterator(iterator,estimatedSize,Spliterator.ORDERED));}public static IntStream stream(Spliterator.OfInt spliterator){return StreamSupport.intStream(spliterator,false);}public static LongStream stream(PrimitiveIterator.OfLong iterator){return stream(iterator,-1);}public static LongStream stream(PrimitiveIterator.OfLong iterator,int estimatedSize){return stream(Spliterators.spliterator(iterator,estimatedSize,Spliterator.ORDERED));}public static LongStream stream(Spliterator.OfLong spliterator){return StreamSupport.longStream(spliterator,false);}public static<T>Stream<T>stream(Iterator<T>iterator){return stream(iterator,-1);}public static<T>Stream<T>stream(Iterator<T>iterator,int estimatedSize){return stream(Spliterators.spliterator(iterator,estimatedSize,Spliterator.ORDERED));}public static<T>Stream<T>stream(Spliterator<T>spliterator){return StreamSupport.stream(spliterator,false);}public static<T>Map<T,Set<Integer>>invert(Collection<T>coll){Map<T,Set<Integer>>map=new HashMap<>();int i=0;for(T t:coll){Set<Integer>set=map.get(t);if(set==null){map.put(t,Collections.singleton(i));}else{if(!(set instanceof LinkedHashSet)){set=new LinkedHashSet<>(set);map.put(t,set);}set.add(i);}i++;}return Collections.unmodifiableMap(map);}public static<T>ArrayList<T>arrayListOfSize(int size){return arrayListOfSize(size,null);}public static<T>ArrayList<T>arrayListOfSize(int size,T element){ArrayList<T>result=new ArrayList<T>(size);for(int i=0;i<size;i++){result.add(element);}return result;}public static<T>int hashAll(Iterator<T>iterator){int hash=1;while(iterator.hasNext()){T obj=iterator.next();hash=hash*31+Objects.hashCode(obj);}return hash;}public static<T>Set<T>asSet(Collection<T>uniqueElements){return asModifiableSet(Collections.unmodifiableCollection(uniqueElements));}public static<T>Set<T>asModifiableSet(Collection<T>uniqueElements){return new AbstractSet<T>(){public int size(){return uniqueElements.size();}public boolean isEmpty(){return uniqueElements.isEmpty();}public boolean contains(Object o){return uniqueElements.contains(o);}public Iterator<T>iterator(){return uniqueElements.iterator();}public Object[]toArray(){return uniqueElements.toArray();}public<T1>T1[]toArray(T1[]a){return uniqueElements.toArray(a);}public boolean add(T t){return uniqueElements.add(t);}public boolean remove(Object o){return uniqueElements.remove(o);}public boolean containsAll(Collection<?>c){return uniqueElements.containsAll(c);}public boolean addAll(Collection<?extends T>c){return uniqueElements.addAll(c);}public boolean retainAll(Collection<?>c){return uniqueElements.retainAll(c);}public boolean removeAll(Collection<?>c){return uniqueElements.removeAll(c);}public void clear(){uniqueElements.clear();}};}public static<T>Collector<T,?,Set<T>>collectToSet(){return Collectors.collectingAndThen(Collectors.toList(),Utils::asSet);}public static<T>ListIterator<T>reverseIterator(List<T>list){return reverseIterator(list.listIterator(list.size()));}public static<T>ListIterator<T>reverseIterator(ListIterator<T>it){return new ListIterator<T>(){public boolean hasNext(){return it.hasPrevious();}public T next(){return it.previous();}public boolean hasPrevious(){return it.hasNext();}public T previous(){return it.next();}public int nextIndex(){return it.previousIndex();}public int previousIndex(){return it.nextIndex();}public void remove(){it.remove();}public void set(T t){it.set(t);}public void add(T t){it.add(t);}};}public static Runnable nonThrowing(ThrowingRunnable<?>r){return()->{try{r.run();}catch(Throwable e){throw new RuntimeException(e);}};}public static<T>Supplier<T>nonThrowing(ThrowingSupplier<T,?>r){return()->{try{return r.get();}catch(Throwable e){throw new RuntimeException(e);}};}public static<T,R>Function<T,R>nonThrowing(ThrowingFunction<T,R,?>r){return(a)->{try{return r.apply(a);}catch(Throwable e){throw new RuntimeException(e);}};}public static<T>Iterable<T>reverseIterable(List<T>list){return()->reverseIterator(list);}private static Map<Class,Class>primitiveClassWrappers=new HashMap<Class,Class>(){{put(boolean.class,Boolean.class);put(byte.class,Byte.class);put(short.class,Short.class);put(char.class,Character.class);put(int.class,Integer.class);put(long.class,Long.class);put(float.class,Float.class);put(double.class,Double.class);}};public static Class<?>primitiveToWrapper(Class<?>clss){return primitiveClassWrappers.getOrDefault(clss,clss);}};

@FunctionalInterface interface ThrowingFunction<T,R,E extends Throwable>{R apply(T t)throws E;};

@FunctionalInterface interface ThrowingRunnable<E extends Throwable>{void run()throws E;};

@FunctionalInterface interface ThrowingSupplier<T,E extends Throwable>{T get()throws E;};

interface VectorElementIterator extends IntIterator{double getValue();double setValue(double value);};

interface IntIterator extends PrimitiveIterator.OfInt{default Iterator<Integer>untripped(){IntIterator it=this;return new Iterator<Integer>(){public boolean hasNext(){return it.hasNext();}public Integer next(){return it.nextInt();}public void remove(){it.remove();}public void forEachRemaining(Consumer<?super Integer>action){it.forEachRemaining(action);}};}};

class VoidOutputStream extends OutputStream{public void write(int b){return;}public void write(byte b[]){return;}public void write(byte b[],int off,int len){return;}};

class VoidPrintStream extends PrintStream{public VoidPrintStream(){super(new VoidOutputStream());}public void write(int b){return;}public void print(char[]buf){return;}public void print(String s){return;}public void print(Object obj){return;}public void println(char[]buf){return;}public void println(String s){return;}public void println(Object obj){return;}public PrintStream format(Locale l,String s,Object...objs){return this;}public PrintStream format(String s,Object...objs){return this;}};