import java.io.IOException; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Comparator; import java.util.NoSuchElementException; import java.util.Objects; import java.util.PriorityQueue; import java.util.TreeSet; public class Main{ public static void main(String[] args){ FastScanner sc = new FastScanner(); Mathplus mp = new Mathplus(); int N = sc.nextInt(); for(int i=N;i>0;i--){ for(int j=0;j[] list; int size; @SuppressWarnings("unchecked") Graph(int N){ size = N; list = new ArrayList[N]; for(int i=0;i(); } } void addEdge(int a,int b){ list[a].add(new Edge(b,1)); } void addWeightedEdge(int a,int b,int c){ list[a].add(new Edge(b,c)); } void addEgdes(int[] a,int[] b){ int size = a.length; for(int i=0;i Q = new ArrayDeque(); Q.add(s); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; long c = e.cost; if(L[w]==-1){ L[w] = L[v] + c; Q.add(w); } } } return L; } long[] dijkstra(int s){ long[] L = new long[size]; for(int i=0;i Q = new PriorityQueue(new SampleComparator()); Q.add(new Pair(0,s)); while(!Q.isEmpty()){ Pair C = Q.poll(); if(visited[(int)C.b]==0){ L[(int)C.b] = C.a; visited[(int) C.b] = 1; for(Edge D:list[(int) C.b]){ Q.add(new Pair(L[(int)C.b]+D.cost,D.to)); } } } return L; } long Kruskal(){ long ans = 0; UnionFindTree UF = new UnionFindTree(size); TreeSet Edges = new TreeSet(new LinkEdgeComparator()); for(LinkEdge e:Edges){ if(!UF.same(e.a,e.b)){ ans += e.L; UF.unite(e.a,e.b); } } return ans; } } class LinkEdge{ long L; int a ; int b; LinkEdge(long l,int A,int B){ L = l; a = A; b = B; } public boolean equals(Object o){ LinkEdge O = (LinkEdge) o; if(O.a==this.a&&O.b==this.b&&O.L==this.L){ return true; }else{ return false; } } public int hashCode(){ return Objects.hash(L,a,b); } } class Edge{ int to; long cost; Edge(int a,long b){ to = a; cost = b; } } class LinkEdgeComparator implements Comparator{ public int compare(LinkEdge P, LinkEdge Q) { long temp = P.L-Q.L; if(temp==0){ if(P.a>Q.a){ return 1; }else{ if(P.b>Q.b){ return 1; }else{ return -1; } } } if(temp>=0){ return 1; }else{ return -1; } } } class Pair{ long a; long b; Pair(long p,long q){ this.a = p; this.b = q; } public boolean equals(Object o){ Pair O = (Pair) o; if(O.a==this.a&&O.b==this.b){ return true; }else{ return false; } } public int hashCode(){ return Objects.hash(a,b); } } class SampleComparator implements Comparator{ public int compare(Pair P, Pair Q) { long temp = P.a-Q.a; if(temp==0){ if(P.b>Q.b){ return 1; }else{ return -1; } } if(temp>=0){ return 1; }else{ return -1; } } } class FastScanner { private final java.io.InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return (minus ? -n : n); }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return (int) (minus ? -n : n); }else{ throw new NumberFormatException(); } b = readByte(); } } } class Mathplus{ int mod = 1000000007; long[] fac = new long[1000001]; boolean isBuild = false; int mindex = -1; int maxdex = -1; void buildFac(){ fac[0] = 1; for(int i=1;i<=1000000;i++){ fac[i] = (fac[i-1] * i)%mod; } isBuild = true; } long max(long[] a){ long max = 0; for(int i=0;ia[i]){ min =a[i]; mindex = i; } } return min; } int min(int[] a){ int min = Integer.MAX_VALUE; for(int i=0;ia[i]){ min =a[i]; mindex = i; } } return min; } long sum(long[] a){ long sum = 0; for(int i=0;i