Geppetto

Ο αγαπημένος σε όλους χαρακτήρας και κουκλοποιός Geppetto άνοιξε μια νέα πιτσαρία, την καλύτερη στην πόλη. Ο Geppetto προσπαθεί να φτιάξει την καλύτερη δυνατή πίτσα, αλλά ταυτόχρονα δεν θέλει να έχει μια μικρή ποικιλία από πίτσες.

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

Υπάρχουν \(Μ\) ζεύγη συστατικών που δεν μπορούν να βρίσκονται στην ίδια πίτσα ταυτόχρονα. Δεδομένων αυτών των περιορισμών, ο Geppetto θέλει να μάθει πόσες διαφορετικές πίτσες μπορεί να φτιάξει. Βοηθήστε τον να απαντήσει σε αυτήν την ερώτηση. Δύο πίτσες θεωρούνται διαφορετικές εάν υπάρχει ένα συστατικό του δείκτη ~i~ που βρίσκεται στη μία πίτσα, αλλά όχι στην άλλη.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς ~N~ και ~M\;(1 \leq N \leq 20,\;1 \leq M \leq 400)~. Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει δύο διαφορετικούς αριθμούς ~a~ και ~b~, που αντιπροσωπεύουν την απαγόρευση ανάμειξης των συστατικών που σημειώνονται με ~a~ και ~b~ στην πίτσα. ~(1 \leq a,\;b \leq N)~. Όλα τα ζεύγη συστατικών δεν είναι απαραίτητα διαφορετικά, κάποιο ζευγάρι μπορεί να συμβεί πολλές φορές.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον αριθμό από τις διαφορετικές πίτσες, δεδομένων των περιορισμών στην εργασία.

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

input

3 2
1 2
2 3

output

5

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

Ο Geppetto μπορεί να φτιάξει πίτσες που αποτελούνται από τα ακόλουθα συστατικά: ~\;,\;1,\;1,\;3,\;2,\;3~. Προσέξτε ότι μια πίτσα μπορεί να είναι χωρίς υλικά.

input

3 0

output

8

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

Ο Geppetto μπορεί να φτιάξει μια πίτσα χρησιμοποιώντας οποιοδήποτε συνδυασμό των συστατικών.

input

3 3
1 2
1 3
2 3

output

4

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

Ο Geppetto μπορεί να φτιάξει μια πίτσα που είτε δεν περιέχει συστατικά είτε περιέχει μόνο ένα συστατικό.