import java.awt.*; import java.util.*; import java.io.*; class TestClass { static class Parser { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Parser(InputStream in) { din = new DataInputStream(in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public long nextLong() throws Exception { long ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = c == '-'; if (neg) c = read(); do { ret = ret * 10 + c - '0'; c = read(); } while (c > ' '); if (neg) return -ret; return ret; } //reads in the next string public String next() throws Exception { StringBuilder ret = new StringBuilder(); byte c = read(); while (c <= ' ') c = read(); do { ret = ret.append((char)c); c = read(); } while (c > ' '); return ret.toString(); } public int nextInt() throws Exception { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = c == '-'; if (neg) c = read(); do { ret = ret * 10 + c - '0'; c = read(); } while (c > ' '); if (neg) return -ret; return ret; } private void fillBuffer() throws Exception { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws Exception { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } } static class OutputWriter { private PrintWriter writer; public OutputWriter(OutputStream stream) { writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter( stream))); } public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); } public void println(int x) { writer.println(x); } public void print(int x) { writer.print(x); } public void println(char x) { writer.println(x); } public void print(char x) { writer.print(x); } public void println(int array[], int size) { for (int i = 0; i < size; i++) println(array[i]); } public void print(int array[], int size) { for (int i = 0; i < size; i++) print(array[i] + " "); } public void println(long x) { writer.println(x); } public void print(long x) { writer.print(x); } public void println(long array[], int size) { for (int i = 0; i < size; i++) println(array[i]); } public void print(long array[], int size) { for (int i = 0; i < size; i++) print(array[i]); } public void println(float num) { writer.println(num); } public void print(float num) { writer.print(num); } public void println(double num) { writer.println(num); } public void print(double num) { writer.print(num); } public void println(String s) { writer.println(s); } public void print(String s) { writer.print(s); } public void println() { writer.println(); } public void printSpace() { writer.print(" "); } public void printf(String format, Object args) { writer.printf(format, args); } public void flush() { writer.flush(); } public void close() { writer.close(); } } static Stack st=new Stack<>(); static HashMap map1=new HashMap<>(); static HashMap map2=new HashMap<>(); static int even=0,odd=0; static class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList(); } void addEdge(int v, int w) { adj[v].add(w); } void DFSUtil(int v, boolean visited[]) { visited[v] = true; // System.out.print(v + " "); Iterator i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } st.push(v); } void DFSUtil2(int v, boolean visited[],HashSet set) { visited[v] = true; set.add(v); Iterator i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil2(n, visited,set); } } void DFS2(){ boolean visited[] = new boolean[V]; while(!st.empty()){ int x=st.pop(); if(visited[x]==false){ HashSet set=new HashSet<>(); DFSUtil2(x,visited,set); int size=set.size(); int count=1; for (int i:set){ if(count