#1395. CNTTREE - Đếm cây

Cho một cây đỉnh, các đỉnh được đánh số từ đến với gốc là đỉnh . Các đỉnh nằm trên đường đi từ đến được gọi là các đỉnh tổ tiên của . Tập các đỉnh nhận làm tổ tiên cùng với các cạnh tương ứng sẽ tạo thành một cây, gọi là cây con gốc . Ta nói cây con gốc đẳng cấu với cây con gốc nếu có thể đánh số lại các đỉnh của cây con gốc sao cho hai cây giống hệt nhau, đồng thời số được dùng để đánh cho đỉnh .

Yêu cầu: Đếm số cặp với sao cho cây con gốc đẳng cấu với cây con gốc .

Dữ liệu vào:

• Dòng đầu chứa ;
• dòng tiếp theo ghi các cạnh của cây .

Dữ liệu ra:

• Một số nguyên là số cặp cây con đẳng cấu.

Ví dụ:

Dữ liệu vào:

5
1 2
1 3
2 4
2 5

Dữ liệu ra:

3

Giới hạn:

• số test có ;
• số test có .