package main import ( "bufio" "container/heap" "fmt" "os" "strconv" ) const inf int = 1 << 25 func main() { sc.Split(bufio.ScanWords) // indexと島を合わせるために孤立した島0を加えておく n := nextInt() + 1 m := nextInt() q := nextInt() bridge := make([]nodes, m) crashed := make(map[int]int) for i := 0; i < m; i++ { bridge[i].a = nextInt() bridge[i].b = nextInt() crashed[bridge[i].a*1000000+bridge[i].b] = inf } crash := make([]nodes, q) for i := 0; i < q; i++ { crash[i].a = nextInt() crash[i].b = nextInt() crashed[crash[i].a*1000000+crash[i].b] = i + 1 } // グラフ g := newGraph(n) for i := 0; i < m; i++ { a := bridge[i].a b := bridge[i].b cost := crashed[a*1000000+b] g[a] = append(g[a], Edge{to: b, time: cost}) g[b] = append(g[b], Edge{to: a, time: cost}) } // 改変ダイクストラ d := g.dijkstar(n, 1) // 最後までつながっている島: -1 // 最初からつながっている島: 0 for i := 2; i < n; i++ { switch d[i] { case inf: fmt.Println("-1") case -1: fmt.Println("0") default: fmt.Println(d[i]) } } } type nodes struct { a, b int } type Edge struct { to int time int } type Graph [][]Edge func newGraph(n int) Graph { g := make(Graph, n) for i := range g { g[i] = make([]Edge, 0) } return g } func (g *Graph) dijkstar(n, s int) []int { d := make([]int, n) // 頂点sからの最短距離 for i := range d { d[i] = -1 } // 優先度(最後につながっているイベントタイム)が大きい島からとりだす que := make(PriorityQueue, 0) heap.Init(&que) d[s] = inf heap.Push(&que, &Item{node: s, time: inf}) for que.Len() > 0 { p := heap.Pop(&que).(*Item) v := p.node // 生存時間が島より短い橋は無視する if d[v] > p.time { continue } for i := 0; i < len((*g)[v]); i++ { // 先の島から伸びてる橋を走査 e := (*g)[v][i] t := min(d[v], e.time) // 新しい経路の生存時間 if d[e.to] < t { d[e.to] = t heap.Push(&que, &Item{time: d[e.to], node: e.to}) } } } return d } // https://golang.org/pkg/container/heap/ // An Item is something we manage in a priority queue. type Item struct { node int // The value of the item; arbitrary. time int // The priority of the item in the queue. // The index is needed by update and is maintained by the heap.Interface methods. index int // The index of the item in the heap. } type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { // We want Pop to give us the highest, not lowest, priority so we use greater than here. return pq[i].time > pq[j].time } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] item.index = -1 // for safety *pq = old[0 : n-1] return item } func (pq *PriorityQueue) update(item *Item, value int, priority int) { item.node = value item.time = priority heap.Fix(pq, item.index) } var sc = bufio.NewScanner(os.Stdin) func nextLine() string { sc.Scan() return sc.Text() } func nextInt() int { i, _ := strconv.Atoi(nextLine()) return i } func min(a, b int) int { if a < b { return a } return b }