Τίτλος	Χρωματισμός μονοπατιών σε γράφο αλυσσίδα
Problem ID	chncolor

Δίνεται μια ευθεία (αλυσσίδα) με Ν διακεκριμένα σημεία (κόμβους) πάνω σε αυτήν, αριθμημένα από 0 εώς Ν-1. Ένα μονοπάτι πάνω στην ευθεία ορίζεται από την αρχή και το τέλος του, δηλαδή τον αριθμό του αρχικού του κόμβου και τον αριθμό του τελικού του κόμβου. Δύο μονοπάτια αλληλεπικαλύπτονται αν έχουν τουλάχιστον δύο κοινούς κόμβους. Για δοσμένα μονοπάτια σε δοσμένη ευθεία, ζητείται ο ελάχιστος αριθμός χρωμάτων που χρειάζονται για να χρωματιστούν τα μονοπάτια, έτσι ώστε δύο οποιαδήποτε μονοπάτια που αλληλεπικαλύπτονται, να μην έχουν το ίδιο χρώμα.

Η είσοδος του προγράμματος (standard input) θα είναι η εξής: Η πρώτη γραμμή θα έχει τον αριθμό των σημείων στην ευθεία (Ν). Η επόμενη γραμμή θα έχει τον αριθμό των μονοπατιών (M) και μετά θα ακολουθούν Μ γραμμές με ένα μονοπάτι η καθεμιά με τον αριθμό του σημείου της αρχής του και τον αριθμό του σημείου του τέλους του.

• θα ισχύει 2<=Ν<=10000 και 1<=Κ<=1000
• Οι αριθμοί σε μια γραμμή χωρίζονται με κενά.
• Ο αρχικός κόμβος κάθε μονοπατιού θα έχει μικρότερο αριθμό από τον τελικό του κόμβο.

Η έξοδος του προγράμματος (standard output) θα είναι ο ελάχιστος αριθμός χρωμάτων.

Παράδειγμα:

Είσοδος:

10
4
1 5
2 7
3 4
8 9

3