Hipercijevi

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τρεις θετικούς ακέραιους αριθμούς: ~N~ ~(1 \le N \le 100\,000)~, τον αριθμό των σταθμών, ~K~ ~(1 \le K \le 1\,000)~, τον αριθμό των σταθμών που διασυνδέει άμεσα οποιοσδήποτε υπερσωλήνας και ~M~ ~(1 \le M \le 1\,000)~, τον αριθμό των υπερσωλήνων.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει την περιγραφή ενός μεμονωμένου υπερσωλήνα: ~K~ θετικοί ακέραιοι αριθμοί, οι ετικέτες των σταθμών που συνδέονται με αυτόν τον υπερσωλήνα.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο ελάχιστο αριθμό σταθμών. Εάν δεν είναι δυνατό να ταξιδέψετε από το σταθμό 1 στον σταθμό ~N~, τυπώστε -1.

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

input

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

output

4

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

Είναι δυνατό να ταξιδέψετε από τον σταθμό 1 στον σταθμό 9 χρησιμοποιώντας μόνο τέσσερις σταθμούς με τους ακόλουθους τρόπους: ~1-3-6-9~ ή ~1-5-6-9~.

input

15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13

output

3