Submit solution

Points: 0.90 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~ .


Comments

Please read the guidelines before commenting.


There are no comments at the moment.