...Σε μία άλλη φάση της πορείας μέσα από την έρημο της Γεδρωσίας μερικοί άντρες ανακάλυψαν λίγο νερό σε μία αβαθή χαράδρα και το έφεραν στον Αλέξανδρο, που προχωρούσε κι αυτός πεζός. Εκείνος τους επαίνεσε, αλλά έχυσε το νερό που του είχαν φέρει μέσα σε κράνος, διότι δεν έφτανε για όλους. Έτσι έδωσε θάρρος στη στρατιά, που είδε ότι όλοι βρίσκονταν στην ίδια μοίρα. Το περιστατικό αυτό αναφέρεται από πολλούς ιστορικούς...
Προκειμένου να ανακαλύψουμε σε ποιο ακριβώς τόπο συνέβη το παραπάνω περιστατικό, αποτυπώσαμε σε ένα χάρτη την πορεία του Μεγάλου Αλεξάνδρου. Γνωρίζουμε λοιπόν για κάθε πόλη την επόμενη πόλη που επισκέφθηκε. Είμαστε επίσης σε θέση να γνωρίζουμε τις ανάγκες του στρατού σε λίτρα νερού για κάθε τέτοια διαδρομή.
Προσπαθούμε να απαντήσουμε σε ερωτήματα του τύπου : Αν ο Αλέξανδρος ξεκίνησε από την πόλη Χ κι ο στρατός μπορεί να κουβαλάει Μ λίτρα νερό ( ανεφοδιάζεται κάθε φορά που φτάνει σε μία πόλη ), πόσες πόλεις διέσχισαν μέχρι να συμβεί το παραπάνω περιστατικό;
Στην πρώτη γραμμή δίνονται 2 αριθμοί, οι Ν ( πλήθος πόλεων ) και Q ( πλήθος ερωτημάτων ).
Ακολουθούν Ν γραμμές που η κάθε μία περιέχει 2 αριθμούς, ai και bi. Η i-οστή απ αυτές τις γραμμές περιέχει τον ai ( πόλη στην οποία πήγαν μετά την πόλη i ) και bi ( ανάγκες σε λίτρα νερού για να πάνε από την πόλη i στην πόλη ai ).
Στη συνέχεια Q γραμμές που η κάθε μία περιέχει 2 αριθμούς, Χi και Μi. Η κάθε γραμμή αντιπροσωπεύει ένα ερώτημα της μορφής : Ξεκινώντας από την πόλη Χi, με ικανότητα να κουβαλάνε Μi λίτρα νερό, πόσες πόλεις διέσχισαν μέχρι να συμβεί το προαναφερθέν περιστατικό ( δηλαδή τα Μi λίτρα που κουβαλούσαν να μην ήταν αρκετά για εκείνη τη διαδρομή );
Q γραμμές, η κάθε μία θα περιέχει έναν αριθμό. Η i-οστη από αυτές τις γραμμές θα αντιπροσωπεύει την απάντηση στο i-οστο ερώτημα, δηλαδή το πλήθος των πόλεων που διέσχισαν μέχρι να τελειώσει το νερό, ή -1 αν ξεκινώντας από την πόλη Χi δεν ήταν δυνατό να τους τελειώσει το νερό σε κανένα σημείο της εκστρατείας.
1 <= N,Q <= 400.000
1 <= bi,Mi <= 10.000.000
1 <= Xi,ai <= N
3 3 2 5 1 3 2 14 2 4 1 5 3 13
2 -1 1
Για να πάνε από την πόλη 1 στην πόλη 2 χρειάζονται 5 λίτρα, από την 2 στην 1 χρειάζονται 3 λίτρα, κι από την 3 στην 2 χρειάζονται 14 λίτρα.
Αν ξεκίνησαν απ την πόλη 2 κουβαλόντας 4 λίτρα νερό, τότε μπόρεσαν να φτάσουν στην πόλη 1, αφού χρειάζονταν μόνο 3 λίτρα νερό. Εκεί ανεφοδιάστηκαν κι έτσι είχαν πάλι 4 λίτρα νερό. Όμως για να πάνε από την πόλη 1 στην πόλη 2 θέλανε 5 λίτρα νερό, κι αφού είχαν μόνο 4, στη διαδρομή αυτή συνέβη το περιστατικό.
Άρα πέρασαν από 2 πόλεις μέχρι να τους τελειώσει το νερό ( την 2 από όπου ξεκίνησαν και την 1 ).
Αν ξεκίνησαν απ την πόλη 1 με 5 λίτρα νερό, τότε μπόρεσαν να πάνε στην πόλη 2, αφού χρειάζονταν 5 λίτρα, εκεί ανεφοδιάστηκαν και ξαναπέρασαν στην 1, από εκεί ανεφοδιάστηκαν και ξαναπήγαν στην 2, κλπ κλπ.
Άρα δε μπορεί να τους τελείωσε το νερό κάπου στη διαδρομή, και για αυτό τυπώνουμε -1.
Αν ξεκίνησαν απ την πόλη 3 με 13 λίτρα νερό, το περιστατικό συνέβη στο δρόμο για την πόλη 2, αφού χρειάζονταν 14 λίτρα νερό για να φτάσουν εκεί.
Άρα πέρασαν από 1 πόλη ( την 3 ) μέχρι να τους τελειώσει το νερό.