35ος ΠΔΠ Καμπ (κοινά)
EVENCYCLE (evencycle)
Πρόβλημα:
Δίνεται ένας μη κατευθυνόμενος γράφος αποτελούμενος από \(N\) κορυφές και \(M\) ακμές. Ζητείται να βρείτε έναν κύκλο με άρτιο πλήθος ακμών, αν υπάρχει.
Αρχεία εισόδου (evencycle.in):
Στην πρώτη γραμμή της εισόδου θα υπάρχει ένας θετικός ακέραιος \(T\), το πλήθος των ερωτημάτων που θα πρέπει να απαντήσετε. Σε καθένα από τα επόμενα \(T\) ερωτήματα, θα υπάρχουν στην πρώτη γραμμή δύο φυσικοί αριθμοί \(N\) και \(M\) χωρισμένοι μεταξύ τους με ένα κενό διάστημα: το πλήθος των κορυφών και το πλήθος των ακμών του γράφου. Θα ακολουθούν \(M\) γραμμές, κάθε μία από τις οποίες θα περιέχει δύο φυσικούς αριθμούς \(U\) και \(V\), χωρισμένους μεταξύ τους με ένα κενό διάστημα, που παριστάνουν μια ακμή μεταξύ των κορυφών \(U\) και \(V\). Θεωρήστε ότι οι κορυφές είναι αριθμημένες από \(1\) μέχρι \(N\) και ότι δε θα δίνονται δύο ακμές που να ενώνουν τις ίδιες κορυφές του γράφου.
Αρχεία εξόδου (evencycle.out):
Η έξοδος θα πρέπει να περιέχει ακριβώς \(T\) γραμμές, που κάθε μία θα περιέχει την απάντηση σε ένα ερώτημα, με τη σειρά που αυτά δίνονται. Η γραμμή της απάντησης θα περιέχει, εναλλακτικά:
- Τη λέξη “cycle”, ακολουθούμενη από έναν άρτιο θετικό ακέραιο αριθμό \(K\) (το πλήθος των ακμών του κύκλου), ακολουθούμενο από \(K\) αριθμούς \(u_1, u_2, \ldots, u_k\). Αυτή η απάντηση σημαίνει ότι βρέθηκε ο ζητούμενος κύκλος. Για να είναι έγκυρη μια τέτοια απάντηση θα πρέπει \(K \ge 4\) (προφανώς μια σκέτη ακμή δε θεωρείται κύκλος), οι αριθμοί \(u_1, u_2, \ldots, u_k\) να είναι ανά δύο διαφορετικοί, να αντιστοιχούν σε κορυφές του κύκλου, να υπάρχει ακμή \((u_i, u_{i+1})\) για κάθε \(1 \le i \lt K\) και επίσης να υπάρχει ακμή \((u_k, u_1)\) για να κλείνει ο κύκλος. Σε περίπτωση που υπάρχουν περισσότεροι κύκλοι με άρτιο πλήθος ακμών, μπορείτε να εκτυπώσετε όποιον από αυτούς θέλετε.
- Τη λέξη “none”, αν δεν υπάρχει κύκλος με άρτιο πλήθος ακμών.
Όλες οι λέξεις και οι αριθμοί σε κάθε γραμμή της εξόδου θα πρέπει να χωρίζονται ανά δύο μεταξύ τους με ένα κενό διάστημα.
Παράδειγμα αρχείου εισόδου - εξόδου:
Για τη διευκόλυνσή σας, στο παράδειγμα που ακολουθεί είναι διαχωρισμένα τα τρία ερωτήματα εισόδου μεταξύ τους.
| evencycle.in | evencycle.out | |
|---|---|---|
| 3 | ||
| 4 5 1 2 1 3 2 3 3 4 4 1 |
cycle 4 3 2 1 4 |  |
| 5 6 1 2 1 3 1 4 1 5 2 3 4 5 |
none |  |
| 7 6 1 7 3 4 4 5 5 6 6 3 5 2 |
cycle 4 6 3 4 5 |  |
Περιορισμοί:
- \(1 \le T \le 10\).
- \(1 \le N \le 100.000\) και \(0 \le M \le 200.000\). Φυσικά θα είναι \(M \le N \cdot \frac{N-1}{2}\).
- \(1 \le U \le N\) και \(1 \le V \le N\) για κάθε δοθείσα ακμή, και επιπλέον \(U \neq V\).
- Το άθροισμα των \(N\) όλων των ερωτημάτων δε θα υπερβαίνει το \(200.000\) και το άθροισμα των \(M\) όλων των ερωτημάτων δε θα υπερβαίνει το \(400.000\).
Subtasks:
- Για περιπτώσεις ελέγχου συνολικής αξίας \(15\%\), θα είναι \(N \le 10\).
- Για περιπτώσεις ελέγχου συνολικής αξίας \(15\%\), θα είναι \(10 \lt N \le 100\) και \(M \le 200\).
- Για περιπτώσεις ελέγχου συνολικής αξίας \(22\%\), οι κορυφές του γράφου θα μπορούν να χρωματιστούν με δύο χρώματα κατά τέτοιο τρόπο ώστε να μην υπάρχει ακμή μεταξύ κορυφών του ίδιου χρώματος.
- Για περιπτώσεις ελέγχου συνολικής αξίας \(11\%\), κάθε κορυφή του γράφου θα συνδέεται το πολύ με δύο άλλες κορυφές.
- Για περιπτώσεις ελέγχου συνολικής αξίας \(15\%\), κάθε κορυφή του γράφου θα συνδέεται το πολύ με τρεις άλλες κορυφές (και θα υπάρχουν κορυφές που συνδέονται ακριβώς με τρεις).
- Για τις υπόλοιπες περιπτώσεις ελέγχου, συνολικής αξίας \(22\%\), κανείς από τους παραπάνω ειδικούς περιορισμούς δε θα ισχύει.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(256\) MB.