Daily Commute

Το Τορόντο έχει ~N~ σταθμούς μετρό, αριθμημένους από το ~1~ έως το ~N~. Ξεκινάτε από το σταθμό ~1~ και κάθε μέρα, πρέπει να φτάσετε στο σταθμό ~N~ για να πάτε στο σχολείο σας.

Υπάρχουν ~W~ δρόμοι μιας κατεύθυνσης μεταξύ των σταθμών, ο ~i~-οστός από τους οποίους σας επιτρέπει να περπατήσετε από το σταθμό ~A_{i}~ σε ένα διαφορετικό σταθμό ~B_i\;(1 \le A_{i}, B_{i} \le N,\;A_{i} \neq B_{i})~ σε ~1~ λεπτό. Μπορεί να υπάρχουν πολλαπλοί δρόμοι που να συνδέουν ένα οποιοδήποτε δεδομένο ζεύγος σταθμών.

Η γραμμή του μετρό ακολουθεί μια συγκεκριμένη διαδρομή μέσω των ~N~ σταθμών, ξεκινώντας από το σταθμό ~1~ και επισκεπτόμενη κάθε σταθμό μία φορά. Αρχικά, η διαδρομή αυτή αποτελείται από τους σταθμούς ~S_{1}~, ~S_{2}~, ~...~, ~S_{N}~ , με αυτή τη σειρά. ~S_{1} = 1~, και ~S_{2}~,~ . . . ~ , ~S_{N}~ είναι μια μετάθεση των ακεραίων ~2~, ~. . .~ , N. Μόνο ένα τρένο του μετρό τη μέρα διατρέχει αυτή τη διαδρομή, το οποίο αναχωρεί από το σταθμό ~1~ στις ~6~ το πρωί και χρειάζεται ~1~ λεπτό για να φτάσει σε κάθε επόμενο σταθμό. Αυτό σημαίνει ότι, ~m~ λεπτά μετά τις ~6~ π.μ., το τρένο θα βρίσκεται στο σταθμό ~S_{m+1}~ (ή στο σταθμό ~S_{N}~ αν ~m \ge N - 1~).

Στη διάρκεια ~D~ ημερών, ωστόσο, η διαδρομή της γραμμής του μετρό θα αλλάζει συνεχώς. Στην αρχή της ~i~-οστής ημέρας, ο ~X_{i}~-οστός σταθμός και ο ~Y_{i}~-οστός σταθμός ~(2 \le X_{i},Y_{i} \le N,\;X_{i} \neq Y_{i})~ στη διαδρομή θα ανταλλάσσονται. Σημειώστε ότι, μετά από κάθε τέτοια αλλαγή, η διαδρομή θα εξακολουθεί να ξεκινά από τον σταθμό ~1~ και θα επισκεφθεί και τους ~N~ σταθμούς μία φορά τον καθένα. Οι αλλαγές θα συνεχίζονται στις ακόλουθες ημέρες- η διαδρομή δεν θα επανέλθει αυτόματα σε ~S_{1}~, ~. . .~. ,~ S_{N}~.

Σε κάθε μία από αυτές τις ~D~ ημέρες, θα θέλατε να προσδιορίσετε πόσο γρήγορα μπορείτε να φτάσετε στο σχολείο, ώστε να αρχίσετε να μαθαίνετε πράγματα. Την ~i~-οστή ημέρα, ξεκινώντας στις ~6~ το πρωί (μετά την ~i~-οστή ενημέρωση της διαδρομής της γραμμής του μετρό), θα ξεκινήσετε το καθημερινό σας ταξίδι ως το σταθμό ~N~. Κάθε λεπτό, μπορείτε είτε να ταξιδέψετε με το μετρό ως την επόμενη στάση του (αν εκείνη τη στιγμή βρίσκεστε στον ίδιο σταθμό με το τρένο και αυτό δεν έχει ήδη ολοκληρώσει τη διαδρομή του), να επιλέξετε να περπατήσετε έναν δρόμο από τον τρέχοντα σταθμό στον οποίο βρίσκεστε, ως έναν άλλο, ή να περιμένετε στον τρέχοντα σταθμό σας. Σημειώστε ότι το ταξίδι σας αρχίζει την ίδια ώρα με την εκκίνηση της διαδρομής του τρένου, πράγμα που σημαίνει ότι μπορείτε να επιλέξετε να ταξιδέψετε αμέσως με το τρένο, αν το επιθυμείτε, και ότι μπορείτε να επιλέξετε να αποχωρήσετε από το τρένο και στη συνέχεια να επιστρέψετε σε αυτό κατά τη διάρκεια του ταξιδιού σας.

Είσοδος

Η πρώτη γραμμή θα περιέχει τρεις ακέραιους αριθμούς, ~N~, ~W~ και ~D~, χωρισμένους με κενά διαστήματα.
Οι επόμενες ~W~ γραμμές θα περιέχουν δύο ακέραιους αριθμούς η καθεμιά, ~A_{i}~ και ~B_{i}\;(1 \le i \le W)~, χωρισμένους με κενά διαστήματα.
Η επόμενη γραμμή θα περιέχει τους ~N~ ακέραιους αριθμούς, ~S_{1}~, ~. . .~ , ~S_{N}~ , χωρισμένους με κενά διαστήματα, οι οποίοι αποτελούν την αρχική μετάθεση των σταθμών.
Οι επόμενες ~D~ γραμμές θα περιέχουν η καθεμιά δύο ακέραιους αριθμούς χωρισμένους με κενό διάστημα, ~X_{i}~ και ~Y_{i}\;(1 \le i \le D)~.

Για ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~3 \le N \le 10~, ~0 \le W \le 10~ και ~1 \le D \le 10~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~3 \le N \le 200~, ~0 \le W \le 200~ και ~1 \le D \le 200~.

Για επιπλέον ~3~ από τους ~15~ διαθέσιμους βαθμούς, ~3 \le N \le 2000~, ~0 \le W \le 2000~ και ~1 \le D \le 2000~.

Για επιπλέον ~8~ από τους ~15~ διαθέσιμους βαθμούς, ~3 \le N \le 200\;000~, ~0 \le W \le 200\;000~ και ~1 \le D \le 200\;000~.

Έξοδος

Η έξοδος θα αποτελείται από ~D~ γραμμές, με έναν ακέραιο ανά γραμμή. Η ~i~-οστή γραμμή θα περιέχει τον ελάχιστο αριθμό λεπτών που απαιτούνται για να φτάσει κανείς στο σταθμό ~N~ την ~i~-οστή ημέρα ~(1 \le i \le D)~.

Παράδειγμα

input

4 3 3
1 2
3 4
4 1
1 4 3 2
3 4
4 2
3 2

output

1
2
3

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

Στην αρχή της πρώτης ημέρας, η διαδρομή της γραμμής του μετρό θα ενημερωθεί ώστε το τρένο να περνάει από τους σταθμούς ~\left[1, 4, 2, 3\right]~, με αυτή τη σειρά. Εκείνη την ημέρα, θα πρέπει απλά να πάρετε το μετρό μέχρι το σταθμό ~4~, διαδρομή διάρκειας ενός λεπτού.

Τη δεύτερη ημέρα, η διαδρομή θα γίνει ~\left[1, 3, 2, 4\right]~, και θα πρέπει να πάρετε το μετρό μέχρι το σταθμό ~3~ (που διαρκεί ~1~ λεπτό) και στη συνέχεια να περπατήσετε μέχρι το σταθμό ~4~ (που διαρκεί άλλο ~1~ λεπτό).

Την τρίτη ημέρα, η διαδρομή θα γίνει ~\left[1, 2, 3, 4\right]~. Μια επιλογή βέλτιστης διαδρομής περιλαμβάνει περπάτημα μέχρι το σταθμό ~2~ (που διαρκεί ~1~ λεπτό), στη συνέχεια επιβίβαση στο τρένο εκεί και μεταφορά με αυτό μέσα από το σταθμό 3 ως το σταθμό ~4~ (που διαρκεί άλλα ~2~ λεπτά).