Bikes vs Cars

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

Υπάρχουν ~N~ σημαντικές τοποθεσίες (αριθμημένες από το ~0~ έως το ~N-1~) στο Lund, μεταξύ των οποίων οι άνθρωποι ταξιδεύουν συχνά. Οι άνθρωποι ταξιδεύουν μεταξύ δύο τοποθεσιών ακολουθώντας μια διαδρομή, η οποία είναι μια ακολουθία δρόμων που πηγαίνει από την πρώτη τοποθεσία στην άλλη. Ένα όχημα (αυτοκίνητο ή ποδήλατο) μπορεί να ταξιδέψει σε ένα μονοπάτι εάν όλες οι σχετικές λωρίδες έχουν τουλάχιστον το ίδιο πλάτος με το όχημα. Κάθε νεόδμητος δρόμος συνδέει δύο από αυτές τις σημαντικές τοποθεσίες και έχει συνολικό πλάτος ~W~. Αυτό το πλάτος μπορεί να κατανεμηθεί αυθαίρετα μεταξύ ποδηλατοδρόμου και λωρίδας αυτοκινήτου. Στο Lund, ορισμένοι μηχανικοί έχουν πρόσφατα εφεύρει αυτοκίνητα και ποδήλατα πλάτους ~0~ (αυτά μπορούν να ταξιδεύουν σε λωρίδες με πλάτος ~0~).

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

Τυπικά, σας δίνονται για κάθε ζεύγος ~i, j (0 \le i < j \le N-1)~ δύο ακέραιες τιμές ~C_{i,j}~ και ~B_{i,j}~. Ο στόχος σας είναι να κατασκευάσετε ένα δίκτυο δρόμων που να συνδέει τις ~N~ τοποθεσίες. Όλοι οι δρόμοι έχουν πλάτος ~W~, αλλά για κάθε δρόμο ~s~ μπορείτε να αποφασίσετε το πλάτος του ποδηλατόδρομου ~b_s~ και αυτό καθορίζει το πλάτος του αυτοκινητόδρομου ~W - b_s~. Το δίκτυο πρέπει να ικανοποιεί τα ακόλουθα:

• Πρέπει να είναι δυνατή η μετακίνηση μεταξύ κάθε ζεύγους τοποθεσιών. Σημειώστε ότι αυτό μπορεί να απαιτεί ποδήλατο ή αυτοκίνητο πλάτους ~0~.
• Για κάθε ζεύγος θέσεων ~i, j~ (όπου ~i < j~), είναι δυνατή η μετακίνηση μεταξύ ~i~ και ~j~ χρησιμοποιώντας μόνο δρόμους των οποίων οι λωρίδες κυκλοφορίας αυτοκινήτων έχουν πλάτος τουλάχιστον ~C_{i,j}~. Επίσης, ~C_{i,j}~ είναι ο μέγιστος αριθμός με αυτή την ιδιότητα. Δηλαδή, για όλες τις διαδρομές μεταξύ των θέσεων ~i~ και ~j~ ισχύει ότι τουλάχιστον ένας από τους δρόμους έχει λωρίδα κυκλοφορίας αυτοκινήτων πλάτους το πολύ ~C_{i,j}~.
• Για κάθε ζεύγος θέσεων ~i, j~ (όπου ~i < j~), είναι δυνατόν να ταξιδέψει κανείς μεταξύ ~i~ και ~j~ χρησιμοποιώντας μόνο δρόμους των οποίων οι λωρίδες ποδηλάτων έχουν πλάτος τουλάχιστον ~B_{i,j}~. Επίσης, ~B_{i,j}~ είναι ο μέγιστος αριθμός με αυτή την ιδιότητα.

Μπορείτε να βοηθήσετε τον κυβερνήτη του Lund να σχεδιάσει ένα τέτοιο οδικό δίκτυο; Επειδή η χρηματοδότηση είναι περιορισμένη, μπορείτε να κατασκευάσετε το πολύ 2023 δρόμους. Μπορείτε να κατασκευάσετε πολλούς δρόμους μεταξύ του ίδιου ζεύγους σημαντικών θέσεων, αλλά δεν μπορείτε να συνδέσετε μια θέση με τον εαυτό της. Όλοι οι δρόμοι μπορούν να χρησιμοποιηθούν και προς τις δύο κατευθύνσεις.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς ~N~ και ~W~, τον αριθμό των σημαντικών θέσεων στο Lund και το πλάτος των δρόμων που μπορείτε να κατασκευάσετε.

Οι επόμενες ~N-1~ γραμμές περιέχουν τους ακέραιους αριθμούς ~C_{i,j}~. Η ~j~-οστή από αυτές τις γραμμές θα περιέχει κάθε ~C_{i,j}~ όπου ~i < j~. Έτσι, η πρώτη γραμμή θα περιέχει μόνο το ~C_{0,1}~, η δεύτερη θα περιέχει το ~C_{0,2}~ και το ~C_{1,2}~, η τρίτη θα περιέχει τα ~C_{0,3}, C_{1,3}, C_{2,3}~ κ.ο.κ..

Οι επόμενες ~N - 1~ γραμμές περιέχουν τους ακέραιους αριθμούς ~B_{i,j}~, με την ίδια μορφή, όπως το ~C_{i,j}~.

Έξοδος

Εάν είναι αδύνατο να κατασκευαστεί ένα τέτοιο οδικό δίκτυο, εκτυπώστε μια γραμμή με τη συμβολοσειρά "NO".

Διαφορετικά, εκτυπώστε μια γραμμή με τον ακέραιο αριθμό ~M~, τον αριθμό των δρόμων του δικτύου σας.

Για κάθε μία από τις επόμενες ~M~ γραμμές, εκτυπώστε τρεις ακεραίους ~u~, ~v~, ~b~, που υποδεικνύουν ότι ένας δρόμος με ποδηλατόδρομο πλάτους ~b~ (και ένας δρόμος για αυτοκίνητα πλάτους ~W - b~) περνάει μεταξύ των ~u~ και ~v~.

Μπορείτε να χρησιμοποιήσετε το πολύ ~2023~ δρόμους. Οι δρόμοι που θα εκδώσετε πρέπει να ικανοποιούν τις εξής προϋποθέσεις: ~0 \le b \le W~, ~0 \le u, v \le N - 1~ και ~u \ne v~. Μπορείτε να χρησιμοποιήσετε πολλούς δρόμους (ενδεχομένως διαφορετικού πλάτους ποδηλατοδρόμου) μεταξύ του ίδιου ζεύγους σημαντικών θέσεων.

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

Περιορισμοί

• ~2 \le N \le 500~
• ~1 \le W \le 10~
• ~0 \le C, B \le W~ για όλα τα ~0 \le i < j \le N - 1~

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	Όλα τα ~C_{i,j}~ είναι ίδια και όλα τα ~B_{i,j}~ είναι ίδια, ~N \le 40~.
2	5	Όλα τα ~C_{i,j}~ είναι ίδια και όλα τα ~B_{i,j}~ είναι ίδια.
3	17	~N \le 40~
4	18	~W = 1~
5	19	Όλα τα ~B_{i,j}~ είναι ίδια.
6	31	Κανένας επιπλέον περιορισμός.

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

input

2 1
1
1

output

2
0 1 0
0 1 1

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

Στο πρώτο παράδειγμα, το πλάτος ενός δρόμου είναι ~1~ και χρειαζόμαστε έναν αυτοκινητόδρομο και έναν ποδηλατόδρομο πλάτους τουλάχιστον ~1~ μεταξύ των θέσεων ~0~ και ~1~. Η λύση είναι να έχουμε δύο ξεχωριστούς δρόμους που να συνδέουν τις τοποθεσίες, μία λωρίδα ποδηλάτων πλάτους ~1~ και μία λωρίδα αυτοκινήτων πλάτους ~1~.

////ΕΙΚΟΝΑ////

input

4 1
0
0 1
0 0 1
1
1 1
1 1 1

output

NO

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

Στο δεύτερο παράδειγμα, το πλάτος ενός δρόμου είναι και πάλι ~1~ και θα πρέπει να υπάρχει ένας δρόμος με ποδηλατόδρομο πλάτους ~1~ μεταξύ κάθε ζεύγους σημαντικών θέσεων και ένας δρόμος μεταξύ των θέσεων ~1~ και ~2~ και ~2~ και ~3~, όπου το πλάτος του αυτοκινητόδρομου είναι ~1~ για κάθε δρόμο. Αυτό έρχεται σε αντίθεση με το γεγονός ότι, καθώς ~C_{1,3} = 0~, δεν θα έπρεπε να υπάρχει μονοπάτι με λωρίδα αυτοκινήτου πλάτους ~1~ από το ~1~ στο ~3~, καθώς μπορούμε απλώς να ενώσουμε τα δύο προαναφερθέντα μονοπάτια για να σχηματίσουμε ένα τέτοιο μονοπάτι. Συνεπώς, δεν είναι δυνατόν να κατασκευαστεί ένα τέτοιο οδικό δίκτυο.

input

6 6
5
4 4
1 1 1
1 1 1 3
1 1 1 5 3
2
3 2
6 2 3
3 2 5 3
3 2 4 3 4

output

8
0 1 1
0 2 3
1 2 2
0 3 6
2 4 5
3 4 3
3 5 1
4 5 4

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

Στο τρίτο παράδειγμα, το παρακάτω οδικό δίκτυο πληροί όλες τις προϋποθέσεις. Για παράδειγμα, θα πρέπει να υπάρχει ένας δρόμος με ελάχιστο πλάτος της λωρίδας αυτοκινήτων \(1 = C_{0,5} μεταξύ της θέσης \)0\( και της θέσης \)5\( (π.χ. ακολουθώντας τη διαδρομή \)0 \rightarrow 2 \rightarrow 4 \rightarrow 5\(), ένας δρόμος όπου η λωρίδα ποδηλάτων έχει ελάχιστο πλάτος \)3 = B_{0,5}\( (π.χ. ακολουθώντας τη διαδρομή \)0 \rightarrow 3 \rightarrow 4 \rightarrow 5~). Ταυτόχρονα μπορεί να ελεγχθεί ότι δεν υπάρχουν μονοπάτια με μεγαλύτερο ελάχιστο πλάτος για καμία από τις συνδέσεις. Σημειώστε ότι υπάρχουν πολλές άλλες λύσεις στο τρίτο παράδειγμα.

////ΕΙΚΟΝΑ////