Bear and Almost Row

Bearland has N cities, numbered 1 through N. For every i between 1 and N-1 inclusive, there is a road between cities i and i+1. There K extra roads: the i-th of them connects two different cities ai and bi. So, there are N-1+K roads in total. All roads are bidirectional. You can assume that every two cities are connected by at most one road. Let f(s, t) denote the distance between cities s and