Venus AUEB Forum

1. Software design
2. Algorithm
3. Information Technology (IT)
4. Programming Battle
5. Interface Designer
6. Short film

• those which look like a valley (V)
• those which look like a mountain (^)

ΧΡΩΜΑΤΙΚΗ ΣΗΜΑΝΣΗ ΤΡΕΝΩΝ
ΠΡΟΒΛΗΜΑ 2ης ΦΑΣΗΣ
16ου ΠΑΝΕΛΛΗΝΙΟΥ ΔΙΑΓΩΝΙΣΜΟΥ ΠΛΗΡΟΦΟΡΙΚΗΣ



Το Ευρωπαϊκό σιδηροδρομικό δίκτυο εξυπηρετεί καθημερινά εκατοντάδες χιλιάδες πολίτες. Το δίκτυο αυτό, συνδέει όλες τις μεγάλες πόλεις της Ευρώπης. Το δίκτυο σχηματικά, αποτελείται από σταθμούς, έναν σε κάθε μεγάλη πόλη και τις γραμμές που τους συνδέουν.

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

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

Γράψτε ένα πρόγραμμα για να βοηθήσετε να χρωματιστούν τα τρένα χρησιμοποιώντας τον ελάχιστο δυνατό διαφορετικό αριθμό χρωμάτων.

Δεδομένα εισόδου
Στην πρώτη γραμμή δίνονται δύο ακέραιοι, Ν και Μ, χωριζόμενοι με ένα κενό, που αντιστοιχούν στο πλήθος των σταθμών και στο πλήθος των διαδρομών. Είναι 1 <= Ν <= 1.000, 1 <= Μ <= 20.000. Ο κάθε σταθμός έχει έναν μοναδικό κωδικό αριθμό, από το 1 εώς το Ν.
Η κάθε μία από τις Μ γραμμές που ακολουθούν περιγράφουν την κάθε διαδρομή.
Η περιγραφή κάθε διαδρομής ξεκινάει με έναν ακέραιο Ρ. Ο αριθμός Ρ είναι ο αριθμός των σταθμών από τους οποίους περνάνε τα τρένα που πραγματοποιούν τη διαδρομή, συμπεριλαμβανομένων και των σταθμών αφετηρίας και τερματισμού. Να θεωρήσετε ότι οι σταθμοί αφετηρίας και τερματισμού είναι πάντα διαφορετικοί μεταξύ τους. Ακολουθούν Ρ ακέραιοι, που αντιστοιχούν στον κωδικό αριθμό των σταθμών αυτών. Όλοι οι αριθμοί στη γραμμή εισόδου χωρίζονται μεταξύ τους με ένα κενό χαρακτήρα.
Σημείωση: Το μέγεθος τους αρχείου εισόδου δεν θα ξεπερνάει τα 2 MB.

Δεδομένα εξόδου
Στην πρώτη γραμμή του αρχείου εξόδου θα πρέπει να γράψετε τον ελάχιστο αριθμό των χρωμάτων που απαιτούνται για το χρωματισμό των διαδρομών, ώστε να πληρούνται οι προδιαγραφές χρωματισμού.
Στη δεύτερη γραμμή του αρχείου εξόδου θα πρέπει να γράψετε Μ ακέραιους αριθμούς, χωριζόμενους με ένα κενό χαρακτήρα. Οι αριθμοί αυτοί θα πρέπει να αναπαριστούν έναν από τους δυνατούς τρόπους χρωματισμού τον τρένων κάθε διαδρομής. Ο πρώτος αριθμός θα αντιστοιχεί στο χρώμα της πρώτης διαδρομής, ο δεύτερος στο χρώμα της δεύτερης κ.ο.κ. Και οι δύο γραμμές θα τελειώνουν με enter.

Παραδείγματα
Input.txt
6 3
3 1 2 3
3 4 5 6
4 1 2 5 6

Output.txt
2
1 1 2

Input.txt
6 4
6 1 2 3 4 5 6
3 2 3 4
2 5 4
2 5 6

Output.txt
3
1 2 3 2

Input.txt
8 4
3 3 2 1
3 2 5 6
4 4 5 6 7
2 8 4

Output.txt
2
1 2 1 2




ΠΡΟΣΟΧΗ!

Το εκτελέσιμο πρόγραμμά σας, θα ονομάζεται trains.exe

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


Σημείωση: Τα δεδομένα εισόδου που θα δίνονται στο πρόγραμμα θα είναι πάντα έγκυρα, όπως περιγράφονται από το πρόβλημα. Έλεγχος εγκυρότητας δεν θα απαιτείται.