Bread First Search

Υπάρχουν ~N~ πόλεις σε ένα δίκτυο ~M~ μη κατευθυνόμενων δρόμων. Κάθε δρόμος συνδέει ένα ζεύγος πόλων. Η κυβέρνηση αποφάσισε να πραγματοποιήσει μια αναζήτηση με βάση το πλάτος (breadth first search), που σημαίνει την εύρεση μιας διάταξης των ~N~ πόλεων τέτοια ώστε αν η σειρά αρχίζει με ~r~:

• Κάθε πόλη εκτός από την ~r~ γειτνιάζει με μια άλλη πόλη που δόθηκε προηγουμένως στη σειρά.

• Οι πόλεις δίνονται με μη φθίνουσα σειρά απόστασης από την ~r~. Εδώ, απόσταση σημαίνει ο ελάχιστος αριθμός δρόμων που πρέπει να διασχίσετε για να φτάσετε σε μια πόλη.

Ωστόσο, κάποιος έκανε κατά λάθος μια αναζήτηση με βάση το ψωμί (bread first search). Βρήκαν την σειρά ~1~, ~2~, ... , ~N~ (αυτό προέκυψε με ταξινόμηση των πόλεων με αυξανόμενη σειρά παραγωγής ψωμιού).

Για να καλύψει αυτό το ντροπιαστικό λάθος, η κυβέρνηση θα ήθελε να κατασκευάσει νέους δρόμους έτσι ώστε το ~1~, ~2~, ... , ~N~ να είναι επίσης μια πιθανή σειρά αναζήτησης με βάση το πλάτος. Οι νέοι δρόμοι μπορούν να κατασκευαστούν μεταξύ δύο οποιωνδήποτε πόλεων. Ποιος είναι ο ελάχιστος δυνατός αριθμός δρόμων που πρέπει να κατασκευαστούν;

Είσοδος

Η πρώτη γραμμή περιέχει τους δύο ακέραιους ~N~ και ~M~ (~1~ ~\le~ ~N~ ~\le~ ~200\,000~, ~0~ ~\le~ ~M~ ~\le~ ~min~(~200\,000~, \(\fraq{N(N-1)}{2}\)).

Η ~i~-οστη από τις επόμενες ~M~ γραμμές περιέχει τους δύο ακέραιους ~a_i~ και ~b_i~ (~1~ ~\le~ ~a_i~, ~b_i~ ~\le~ ~N~), που αντιπροσωπεύουν τα δύο τελικά σημεία του ~i~-οστου δρόμου. Είναι εγγυημένο ότι ~a_i~ ~\ne~ ~b_i~ και υπάρχει το πολύ ένας δρόμος μεταξύ δύο οποιωνδήποτε πόλεων.

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~200~.

Για επιπλέον ~6~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~5\,000~.

Έξοδος

Σε μία μοναδική γραμμή, εκτυπώστε τον ελάχιστο αριθμό δρόμων που πρέπει να κατασκευαστούν.

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

input

2 0

output

1

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

Για να είναι το ~1~,~2~ μια σειρά αναζήτησης με βάση το πλάτος, πρέπει να κατασκευαστεί ένας δρόμος μεταξύ της πόλης ~1~ και ~2~.

input

6 3
1 3
2 6
4 5

output

2

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

Χτίζοντας ένα δρόμο μεταξύ ~1~ και ~2~ και ένα δρόμο μεταξύ ~1~ και ~4~, η σειρά των αποστάσεων γίνεται ~0~,~1~,~1~,~1~,~2~,~2~ η οποία είναι σε μη φθίνουσα σειρά.