import java.util.*; class Edge { public Node node; // neighbor at "this end" of this edge public Edge back; // node at the "other end" of this edge public int count; // number of nodes reachable via "this end" of the edge public Edge(Node n, Edge b) { node = n; back = b; count = 0; } } class Node { public int id; public ArrayList adj; public int pairs; public Node(int i) { id = i; adj = new ArrayList(); pairs = 0; } } public class Keeping { // For each edge, determine number of nodes on either side of the edge. // Each node keeps a list of edges (i.e., ptrs to adjacent nodes) along // with number of nodes associated with the "other side" of that edge. // This is computed via DFS. public static Scanner in; public static int n; public static Node[] node; public static boolean[] visited; public static void main(String[] args) { in = new Scanner(System.in); n = in.nextInt(); node = new Node[n+1]; visited = new boolean[n+1]; for (int i = 0; i <= n; i++) { node[i] = new Node(i); } for (int i = 0; i < n; i++) { int from = in.nextInt(); int to = in.nextInt(); Edge fwd = new Edge(node[to],null); Edge back = new Edge(node[from],fwd); fwd.back = back; node[from].adj.add(fwd); node[to].adj.add(back); } int critnode = findCrit(); //display(); //dump(); //System.out.println("Critical node: " + critnode+", pairs = " // + node[critnode].pairs); } public static int findCrit() { Arrays.fill(visited,false); int temp = dfs(node[0]); if (temp != n+1) { System.out.println("DFS did not count all nodes"); } int max = 0; int maxnode = -1; int dup = -1; for (int i = 0; i <= n; i++) { Node nd = node[i]; nd.pairs = 0; int sum = 0; for (Edge e: nd.adj) { sum += e.count; nd.pairs += e.count*(n-sum); } if (max < nd.pairs) { max = nd.pairs; maxnode = i; dup = -1; } else if (max == nd.pairs) { dup = i; } } if (dup == maxnode) { System.out.println("Duplicate critical junction: " + dup + " " + maxnode); } //System.out.println("Critical: " + maxnode); Collections.sort(node[maxnode].adj, (a,b) -> new Integer(b.count).compareTo(new Integer(a.count))); int m1 = node[maxnode].adj.get(0).count; int m2 = node[maxnode].adj.get(1).count; System.out.println(max+" "+(max-m1*m2)); return maxnode; // for now! } // Count all nodes reachable from this node via the dfs, excluding // already-visited nodes. public static int dfs(Node nd) { if (visited[nd.id]) return 0; visited[nd.id] = true; int sum = 1; // count this node // Try to extend the dfs to neighboring nodes: for (Edge ed: nd.adj) { ed.count = dfs(ed.node); ed.back.count = n+1-ed.count; sum += ed.count; } return sum; } public static void display() { Arrays.fill(visited,false); dfsdisp(node[0]); } public static void dfsdisp(Node k) { if (visited[k.id]) return; visited[k.id] = true; if (k.adj.size()==1) { System.out.println("Node " + k.id + " is a leaf."); } else { System.out.println("Node " + k.id); } for (Edge ed: k.adj) { if (!visited[ed.node.id]) { System.out.print("..Visiting edge " + k.id + " to " + ed.node.id); System.out.print(" with count = " + ed.count); System.out.println("; backedge count = "+ed.back.count); dfsdisp(ed.node); } } } public static void dump() { for (int i = 0; i <= n; i++) { System.out.println("Node " + i + ":"); for (Edge e: node[i].adj) { System.out.println(" edge from " + e.back.node.id + " to " + e.node.id +" has count = " + e.count); } } } }