p016.
骨牌接龍
Content
文文有 𝑛 張骨牌，每張骨牌的兩端各有一個整數，例如 (𝑎, 𝑏)。他喜歡玩一個遊戲，規則如下：
-
如果兩張骨牌的兩端有相同的數字，就可以將這兩張骨牌接在一起，形成骨牌串。
-
骨牌可以任意旋轉，也就是說 (𝑎, 𝑏) 可以當作 (𝑏, 𝑎) 使用。
現在文文想挑戰一個任務：
選定兩張骨牌 𝑠, 𝑡，從骨牌 𝑠 出發，想辦法一路接下去，最後與骨牌 𝑡 連接起來。她想知道，中間最少還需要接幾張骨牌，才能讓這兩張骨牌透過連接串在一起？
請你幫她計算這個最少所需骨牌數量。如果無法接起來，請輸出 -1。
Input
輸入的第一行是一個整數 𝑛，代表文文手上共有 𝑛 張骨牌（2 ≤ 𝑛 ≤ 105）。
接下來共有 𝑛 行，每行兩個整數 𝑎𝑖、𝑏𝑖 (0 ≤ 𝑎𝑖, 𝑏𝑖 < 105），代表一張骨牌的兩端數字。
其中：
-
第一張骨牌是起始骨牌；
-
第二張骨牌是目標骨牌；
-
剩下的 𝑛-2 張骨牌可作為中繼使用。
Output
輸出一個整數，表示最少還需要接幾張骨牌才能讓骨牌 𝑠 和骨牌 𝑡 接在一起。若無法接在一起，請輸出 -1。
Sample Input
#1
5 25 13 6 32 6 43 25 19 25 43
Sample Output
#1
2
Sample Input
#2
3 1 2 3 4 5 6
Sample Output
#2
-1
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint ：
範例一：如題敘圖片。
範例二：三張骨牌都不能連接。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||