import java.io.*; import java.util.*; public class Main { public static void findcount(HashMap<String , String> map){ //make a hashmap to store tree information and store root as ceo HashMap<String , HashSet<String>> tree = new HashMap<>(); String ceo = ""; //traverse the map and fill the tree for(String emp: map.keySet()){ //emp = employee , man = manager String man = map.get(emp); if(man.equals(emp)) ceo = man; else{ //if manager already exists if(tree.containsKey(man)){ tree.get(man).add(emp); } else{ HashSet<String> emps = new HashSet<>(); emps.add(emp); tree.put(man,emps); } } } // make a result Hashmap to store employee:employees under them //write getsize() recurisive tree function to find employees under manager and pass ceo as root HashMap<String, Integer> result = new HashMap<>(); getsize(tree , ceo , result); for(String emp : result.keySet()) System.out.println(emp + " " + result.get(emp)); } //this is a normal getsize recursive functions in general trees public static int getsize(HashMap<String , HashSet<String>> tree, String man , HashMap<String, Integer> result){ //if it doesn't exist in the tree its a leaf node with 0 under employees if(tree.containsKey(man) == false){ result.put(man,0); return 1; } int size = 0; //traversing the tree for(String emp : tree.get(man)){ int cs = getsize(tree,emp,result); size += cs; } result.put(man,size); //putting size infront of that employee return size+1; //return size and +1 including that employee } public static void main(String[] args){ Scanner scn = new Scanner(System.in); int n = scn.nextInt(); HashMap<String , String>map = new HashMap<String , String>(); for(int i=0 ; i < n ; i++) map.put(scn.next(),scn.next()); findcount(map); } }