0 Judge
Code: 0
時間過得很快到了22世紀，發明了一種傳送們可以在瞬間從a地傳送到b地，讓整個城市交通運輸更加便利了，但由於傳送們製作費用比較高，所以不能在所有地方都建造，只有固定幾個地方有，阿源想要計算出到各地的時間，以便他計算運費。 假設阿源的位子在$1$，且這座城市起初是由$m$條單向的道路所建造而成的，通過每條道路的時間皆為$1$單位。 之後政府建造了$k$個傳送門，這個傳送門是單向的，且通過這個門的時間為$0$單位。
輸入的第一行包含一個正整數 $T(T\leq 10)$，代表接下來有 $T$ 個測試資料。 每筆測試資料第一行會有三個正整數 $n(\leq 100000)$ ， $m(\leq 1000000)$，$k(\leq 1000000)$，代表這座城市有$n$個點，原本有$m$條單向道路，及有$k$個傳送門。 接下來會有$m+k$行，分別有兩個正整數 $u$及$v$。 前$m$行代表，有一條單向道路從$u$到$v$ 後面$k$行代表，有一個傳送門可以將人從$u$傳送到$v$。 兩個點間可能會同時有道路及傳送門可以到達。 此題輸入資料量較大，請用較快的輸入方法
請輸出$n$個數字，第$i$個數字代表從第$1$點到第$i$點最短的時間，如果無法到達請輸出$-1$，而阿源的起點$1$的時間為$0$。
$m = 0$
$n \leq 100000,m \leq 100000,k\leq 100000$
無其他限制