{"problem":{"name":"D. Fight Against Traffic","description":{"content":"Little town Nsk consists of _n_ junctions connected by _m_ bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get fro","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF954D"},"statements":[{"statement_type":"Markdown","content":"Little town Nsk consists of _n_ junctions connected by _m_ bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.\n\nIn order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction _s_ to work located near junction _t_. Thus, he wants to build a new road in such a way that the distance between these two junctions won't decrease.\n\nYou are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between _s_ and _t_ won't decrease.\n\n## Input\n\nThe firt line of the input contains integers _n_, _m_, _s_ and _t_ (2 ≤ _n_ ≤ 1000, 1 ≤ _m_ ≤ 1000, 1 ≤ _s_, _t_ ≤ _n_, _s_ ≠ _t_) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The _i_\\-th of the following _m_ lines contains two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_), meaning that this road connects junctions _u__i_ and _v__i_ directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.\n\n## Output\n\nPrint one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won't decrease the distance between junctions _s_ and _t_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"小城 Nsk 由 #cf_span[n] 个交叉口和 #cf_span[m] 条双向道路组成。每条道路连接两个不同的交叉口，且任意两个交叉口之间至多有一条道路。任意两个交叉口之间都可以通过这些道路相互到达。两个交叉口之间的距离等于连接它们的路径中道路数量的最小值。\n\n为了改善交通系统，市议会要求市长修建一条新道路。但问题是，市长刚刚买了一辆漂亮的新车，他非常喜欢从家（位于交叉口 #cf_span[s] 附近）到工作地点（位于交叉口 #cf_span[t] 附近）的驾车体验。因此，他希望修建一条新道路，使得交叉口 #cf_span[s] 和 #cf_span[t] 之间的距离不会减少。\n\n你的任务是计算有多少对未被道路直接连接的交叉口，使得在这两交叉口之间修建一条新道路后，交叉口 #cf_span[s] 和 #cf_span[t] 之间的距离不会减少。\n\n输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[s] 和 #cf_span[t]（#cf_span[2 ≤ n ≤ 1000], #cf_span[1 ≤ m ≤ 1000], #cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t]）——分别表示 Nsk 的交叉口数量、道路数量，以及市长家和工作地点所在的交叉口编号。接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n], #cf_span[ui ≠ vi]），表示这条道路直接连接交叉口 #cf_span[ui] 和 #cf_span[vi]。保证任意两个交叉口之间存在路径，且没有两条道路连接相同的交叉口对。\n\n输出一个整数——满足条件的、未被直接道路连接的交叉口对的数量，即在这些交叉口之间修建新道路后，交叉口 #cf_span[s] 和 #cf_span[t] 之间的距离不会减少。\n\n## Input\n\n输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[s] 和 #cf_span[t]（#cf_span[2 ≤ n ≤ 1000], #cf_span[1 ≤ m ≤ 1000], #cf_span[1 ≤ s, t ≤ n], #cf_span[s ≠ t]）——分别表示 Nsk 的交叉口数量、道路数量，以及市长家和工作地点所在的交叉口编号。接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui, vi ≤ n], #cf_span[ui ≠ vi]），表示这条道路直接连接交叉口 #cf_span[ui] 和 #cf_span[vi]。保证任意两个交叉口之间存在路径，且没有两条道路连接相同的交叉口对。\n\n## Output\n\n输出一个整数——满足条件的、未被直接道路连接的交叉口对的数量，即在这些交叉口之间修建新道路后，交叉口 #cf_span[s] 和 #cf_span[t] 之间的距离不会减少。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = n $, $ |E| = m $.  \nLet $ s, t \\in V $, $ s \\ne t $, denote the source and target junctions.  \nLet $ d(u, v) $ denote the shortest path distance (number of edges) between vertices $ u $ and $ v $ in $ G $.  \nLet $ D = d(s, t) $ be the original distance between $ s $ and $ t $.\n\n**Constraints**  \n1. $ 2 \\le n \\le 1000 $  \n2. $ 1 \\le m \\le 1000 $  \n3. $ 1 \\le s, t \\le n $, $ s \\ne t $  \n4. $ G $ is connected and simple (no multiple edges, no self-loops).\n\n**Objective**  \nCompute the number of unordered pairs $ \\{u, v\\} \\notin E $, $ u \\ne v $, such that adding edge $ (u, v) $ to $ G $ results in a graph $ G' $ where:  \n$$\nd_{G'}(s, t) \\ge d_G(s, t)\n$$  \nThat is, the new edge does not reduce the shortest distance between $ s $ and $ t $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF954D","tags":["dfs and similar","graphs","shortest paths"],"sample_group":[["5 4 1 5\n1 2\n2 3\n3 4\n4 5","0"],["5 4 3 5\n1 2\n2 3\n3 4\n4 5","5"],["5 6 1 5\n1 2\n1 3\n1 4\n4 5\n3 5\n2 5","3"]],"created_at":"2026-03-03 11:00:39"}}