Dom

Σε έναν οίκο ευγηρίας, ~N~ ηλικιωμένοι βλέπουν τηλεόραση. Το τηλεοπτικό πρόγραμμα αποτελείται από ~M~ κανάλια που δηλώνονται με αριθμούς από το 1 έως το ~M~. Καθένας από τους συνταξιούχους έχει το δικό του αγαπημένο και μισητό τηλεοπτικό κανάλι.

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

Φυσικά, μετά από μια αλλαγή καναλιού, είναι πιθανό ένας άλλος συνταξιούχος να βρει το νέο κανάλι αφόρητο, οπότε θα αλλάξει αυτό το κανάλι. Δεδομένου του γεγονότος ότι οι συνταξιούχοι είναι πεισματάρηδες, αυτό μπορεί να συνεχιστεί επ' αόριστον.

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τρεις ακέραιους αριθμούς ~N,\;M~ και ~P\;(1 \leq N,\;M \leq 10^5,\;1 \leq P \leq M)~, τον αριθμό των συνταξιούχων, τον αριθμό των τηλεοπτικών καναλιών και το αρχικό κανάλι που εμφανίζεται στην τηλεόραση.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει δύο ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \leq a_i,\;b_i \leq M,\;a_i \neq b_i)~, το αγαπημένο και μισητό κανάλι κάθε συνταξιούχου.

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

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό αλλαγών καναλιού. Αν οι αλλαγές συνεχιστούν επ' αόριστον, τυπώνουμε -1.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~50~% των συνολικών πόντων, θα έχει ~1 \leq N,\;M \leq 10^3~ .

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

input

3 4 2
1 2
2 3
3 2

output

1

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

Αρχικά, το κανάλι 2 ήταν στην τηλεόραση. Αυτό το κανάλι ενοχλεί τον μικρότερο και τον μεγαλύτερο συνταξιούχο, οπότε ο μικρότερος σηκώνεται με ενθουσιασμό και αλλάζει κανάλι για να μπορούν όλοι να παρακολουθούν το κανάλι 1 μαζί.

input

3 3 1
1 2
2 3
3 1

output

-1

input

4 5 2
1 3
2 3
3 2
5 1

output

3