Στην Χελενικούπολη όλες οι λίμνες, οι οποίες έχουν στις όχθες τους σπιτάκια, έχουν μια περίεργη ιδιότητα: κάθε δύο μη γειτονικά σπιτάκια ενώνονται με δρομολόγιο αν και μόνο αν τα αμέσως στη σειρά επόμενα σπιτάκια (ωρολογιακά) ΔΕΝ ενώνονται με δρομολόγιο. Σε όρους γραφοθεωρίας, κάθε λίμνη μπορούμε να τη φανταστούμε σαν έναν γράφο με N κόμβους 0,1,..n-1 , έτσι ώστε ο κόμβος i να ενώνεται με τον (i+1) mod N, αλλά και ο κόμβος i να ενώνεται με τον j ( j-i > 1 ) αν και μόνο αν ο κόμβος (i+1) mod N ΔΕΝ ενώνεται με τον κόμβο (j+1) mod N. Δεδομένης της περιγραφής μιας λίμνης στη Xελενικούπολη, θέλουμε να απαντήσουμε σε Q ερωτήσεις της μορφής query(i,j): θέλουμε να διαπιστώσουμε ποιο είναι το δρομολόγιο μεταξύ των i,j με το ελάχιστο αριθμό ακμών. Βέβαια, κάποιοι έξυπνοι κάτοικοι παρατήρησαν ότι λόγω της πολύ όμορφης ιδιότητας της πόλης, δεν χρειάζεται να δωθούν όλες οι ακμές του γράφου, παρά μερικές από αυτές, οπότε και εμείς για οικονομία χώρου και χρόνου λέμε να μην πολυλογούμε με περιττές πληροφορίες(έξυπνοι άνθρωποι είστε άλλωστε!).
Στην πρώτη γραμμή δίνεται ο αριθμός Ν που αντιστοιχεί στον αριθμό των κόμβων του γράφου. Στη δεύτερη γραμμή δίνεται ο αριθμός M, ο οποίος αντιστοιχεί στο πλήθος των γειτόνων του κόμβου v_0( εξαιρούνται οι κόμβοι N-1 και 1). Στις επόμενες M γραμμές ακολουθούν οι γείτονες του 0, ένας σε κάθε γραμμή( παραλείπονται οι Ν-1, 1). Στην επόμενη γραμμή υπάρχει ένας ακέραιος αριθμός Q. Στις επόμενες Q γραμμές έχουμε 2 αριθμούς ανά γραμμή, που αντιστοιχούν στα ορίσματα του query.
Q γραμμές με έναν ακέραιο πάνω η καθεμία, τον ελάχιστο αριθμό ακμών για να φτάσουμε από τον έναν κόμβο στον άλλο.
1<= Ν <=5.000, 1<= Q <= 1.000.000
4 1 2 4 0 1 1 2 0 2 1 3
1 1 1 2