Quang Đạt được cho một danh sách ~F~ chuyến bay một chiều giữa ~C~ thành phố (đánh số từ ~0~ đến ~C-1~). Anh ta muốn thăm ~T~ thành phố đầu tiên (từ ~0~ đến ~T-1~). Nhiệm vụ của bạn là tìm số lần di chuyển ít nhất giữa các thành phố để Quang Đạt hoàn thành mục tiêu.

Quang Đạt sống ở thành phố ~0~. Do đó chuyến đi của anh ta phải bắt đầu và kết thúc ở thành phố ~0~. Một thành phố có thể được thăm nhiều lần.

Dữ liệu đảm bảo luôn bạn luôn tìm được đường bắt đầu và kết thúc tại thành phố ~0~ và đi qua tất cả các thành phố từ ~0~ đến ~T-1~.

Input

• Dòng đầu chứa ~3~ số nguyên ~C~, ~T~ và ~F~.
• ~F~ dòng tiếp chứa ~2~ số nguyên ~a~, ~b~ thể hiện đường đi một chiều từ ~a~ đến ~b~.

Output

In ra số nguyên duy nhất là số lần di chuyển ít nhất để Quang Đạt hoàn thành mục tiêu.

Giới hạn

• ~3 \le T \le 8~
• ~T \le C \le 5000~
• ~C \le F \le 100000~
• Trong ~60\%~ test: ~C \le 80~
• Trong ~30\%~ test: ~T \le 5~, ~C \le 10~

Sample Input

7 4 12
0 5
0 4
1 0
1 2
2 6
3 0
3 6
4 3
4 5
6 1
6 2
6 5

Sample Output

7

Note

Trong ví dụ, có ~7~ thành phố, Fred chỉ cần thăm các thành phố ~0~, ~1~, ~2~, ~3~. Nếu anh ta thăm theo thứ tự:

~0 \rightarrow 4 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 6 \rightarrow 1 \rightarrow 0~ Anh ta chỉ cần di chuyển ~7~ lần, và đây chính là lộ trình ngắn nhất có thể để thăm hết các thành phố từ ~0~ đến ~3~ .