Tree Decorations

Ο Mateo βρήκε τα τέλεια διακοσμητικά για το χριστουγεννιάτικο δέντρο του - περισσότερα δέντρα!

Συγκεκριμένα, το χριστουγεννιάτικο δέντρο του είναι ένα ριζωμένο δέντρο ~T~ με, αρχικά, ~M~ κόμβους, οι οποίοι είναι όλοι βαμμένοι πράσινοι. Έχει επίσης ένα άλλο ριζωμένο δέντρο ~D~, το οποίο χρησιμοποιεί ως πρότυπο για τα διακοσμητικά του. Ο Mateo ακολουθεί την παρακάτω διαδικασία για να τοποθετήσει όλα τα διακοσμητικά του:

• Για κάθε κόμβο ~i~ του ~D~, δημιουργεί ένα αντίγραφο του υποδέντρου με ρίζα τον κόμβο ~i~. Έστω ότι αυτό το αντίγραφο είναι το ~C_i~. Στη συνέχεια, βάφει τους κόμβους του ~C_i~ κόκκινους. Τέλος, επιλέγει έναν πράσινο κόμβο του ~T~ ως γονέα της ρίζας του ~C_i~, συνδέοντάς τους με μια ακμή.

Αφού τοποθετήσει όλα τα διακοσμητικά, τότε το ~T~ περιέχει συνολικά ~N~ κόμβους. Δυστυχώς, συνειδητοποίησε ότι είχε ξεχάσει να καταγράψει το δέντρο ~D~! Ακόμη χειρότερα, έριξε κατά λάθος νερό πάνω στο ~T~, με αποτέλεσμα να ξεθωριάσουν όλα τα χρώματα των κόμβων! Μετά από όλα αυτά, αριθμεί τη ρίζα του ~T~ με ~1~ και στη συνέχεια αριθμεί τους υπόλοιπους κόμβους, από ~2~ έως ~N~.

Η μόνη πληροφορία που έχει πλέον είναι η τελική μορφή του ~T~, καθώς και η τιμή του ~M~. Βοηθήστε τον να βρει πόσα διαφορετικά δέντρα ~D~ θα μπορούσε να είχε χρησιμοποιήσει, θεωρώντας δύο δέντρα διαφορετικά αν διαφέρουν ως προς τη δομή τους.

Δύο ριζωμένα δέντρα ~A~ και ~B~ λέγονται δομικά πανομοιότυπα αν και μόνο αν έχουν τον ίδιο αριθμό κόμβων ~S~ και υπάρχει τρόπος να αριθμηθούν οι κόμβοι του ~A~ από ~1~ έως ~S~ και οι κόμβοι του ~B~ από ~1~ έως ~S~, έτσι ώστε:

• Οι ρίζες τους να έχουν τον ίδιο αριθμό.
• Οι κόμβοι με αριθμούς ~x~ και ~y~ στο ~A~ να συνδέονται με ακμή αν και μόνο αν οι κόμβοι με αριθμούς ~x~ και ~y~ στο ~B~ συνδέονται με ακμή.

Σε κάθε άλλη περίπτωση, τα δέντρα ~A~ και ~B~ θεωρούνται δομικά διαφορετικά.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους ~N~ και ~M~, χωρισμένους με ένα κενό.

Οι επόμενες ~N - 1~ γραμμές θα περιέχουν από δύο ακέραιους ~u_i~ και ~v_i~ (~1 \le u_i, v_i \le N~, ~u_i \ne v_i~), οι οποίοι περιγράφουν μια ακμή του ~T~ που συνδέει τους κόμβους ~u_i~ και ~v_i~. Σημειώστε ότι το ~T~ έχει ρίζα τον κόμβο ~1~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμοι 25 βαθμοί:

Βαθμοί	Όρια του N	Όρια του M
~2~	~2 \le N \le 10~	~M = 1~
~3~	~2 \le N \le 200~	~M = 1~
~2~	~2 \le N \le 500.000~	~M = 1~
~6~	~2 \le N \le 200~	~1 \le M < N~
~4~	~2 \le N \le 2000~	~1 \le M < N~
~8~	~2 \le N \le 500.000~	~1 \le M < N~

Έξοδος

Εκτυπώστε τον αριθμό των διαφορετικών δέντρων ~D~ που θα μπορούσε να είχε χρησιμοποιήσει, θεωρώντας δύο δέντρα διαφορετικά αν διαφέρουν ως προς τη δομή τους.

Παραδείγματα

input

8 3
1 2
1 3
1 4
2 5
2 6
3 7
3 8

output

1

Επεξήγηση του πρώτου παραδείγματος:

Μπορεί να αποδειχθεί ότι το μοναδικό πιθανό δέντρο ~D~ είναι το εξής:

Μπορούμε να δημιουργήσουμε το ~T~ με τον ακόλουθο τρόπο:

Στο παραπάνω διάγραμμα, τα κόκκινα τμήματα είναι τα διακοσμητικά που προστέθηκαν, ενώ το πράσινο, συμπαγές τμήμα αντιπροσωπεύει την αρχική μορφή του ~T~. Οι διακεκομμένες γραμμές αντιπροσωπεύουν τις ακμές που συνδέουν τα διακοσμητικά με το δέντρο.

input

14 5
1 2
1 3
3 4
3 5
1 6
6 7
7 8
7 9
2 10
10 11
10 12
10 13
10 14

output

2

Επεξήγηση του δεύτερου παραδείγματος:

Η πρώτη πιθανή επιλογή για το ~D~ είναι η εξής:

Χρησιμοποιώντας αυτό το δέντρο, μπορούμε να δημιουργήσουμε το ~T~ με τον ακόλουθο τρόπο:

Η δεύτερη πιθανή επιλογή για το ~D~ είναι η εξής:

Χρησιμοποιώντας αυτό το δέντρο, μπορούμε να δημιουργήσουμε το ~T~ με τον ακόλουθο τρόπο: