import java.util.*; class root{ int self; ArrayList<root> link = new ArrayList<root>(); public root(int n) { self=n; } public root() { } } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int i =0;i<t;i++) { int n=in.nextInt(); ArrayList<root> al =new ArrayList<root>(); for(int j =0;j<n-1;j++) { int a=in.nextInt(); int b =in.nextInt(); root ra =new root(); root rb =new root(); boolean ifhasa=false; boolean ifhasb=false; for(root R:al) { if(R.self==a) { ifhasa=true;; ra=R; } if(R.self==b) { ifhasb=true; rb=R; } } if(!ifhasa) { ra = new root(a); } if(!ifhasb) { rb = new root(b); } ra.link.add(rb); rb.link.add(ra); if(!al.contains(ra)) { al.add(ra); } if(!al.contains(rb)) { al.add(rb); } } /*System.out.println(al.size()); int l = 0; for(root r :al) { l+=r.link.size(); } System.out.println(l/2);*/ //System.out.println(battle(al)); if(battle(al)) { System.out.println("Alice"); }else { System.out.println("Bob"); } } } public static boolean battle(ArrayList<root> AL) { ArrayList<root> al =(ArrayList<root>)AL.clone(); if(al.size()==1) { return false; } for(int i =0;i<al.size();i++) { for(int j =0;j<al.size();j++) { if(i!=j && iflinkboth(al.get(i),al.get(j))) { al.get(i).link.remove(al.get(j)); al.get(j).link.remove(al.get(i)); for(int l =0;l<al.size();l++) { if(!iflinktoa(al.get(l))) { al.remove(l); l--; } } if(!battle(al)) { return true; }else { al=(ArrayList<root>)AL.clone(); continue; } } } } return false; } public static boolean iflinktoa(root r) { if(r.self==1) { return true; }else { for(root R:r.link) { R.link.remove(r); if(iflinktoa(R)) { R.link.add(r); return true; }else { R.link.add(r); } } return false; } } public static boolean iflinkboth(root a,root b) { if(a.link.contains(b) && b.link.contains(a)) { return true; } return false; } } |
Double click to view unformatted code.