{"raw_statement":[{"iden":"statement","content":"It's the turn of the year, so Bash wants to send presents to his friends. There are _n_ cities in the Himalayan region and they are connected by _m_ bidirectional roads. Bash is living in city _s_. Bash has exactly one friend in each of the other cities. Since Bash wants to surprise his friends, he decides to send a Pikachu to each of them. **Since there may be some cities which are not reachable from Bash's city, he only sends a Pikachu to those friends who live in a city reachable from his own city**. He also wants to send it to them as soon as possible.\n\nHe finds out the minimum time for each of his Pikachus to reach its destination city. Since he is a perfectionist, he informs all his friends with the time their gift will reach them. A Pikachu travels at a speed of 1 meters per second. His friends were excited to hear this and would be unhappy if their presents got delayed. Unfortunately Team Rocket is on the loose and they came to know of Bash's plan. They want to maximize the number of friends who are unhappy with Bash.\n\nThey do this by destroying exactly one of the other _n_ - 1 cities. This implies that **the friend residing in that city dies, so he is unhappy as well**.\n\nNote that **if a city is destroyed, all the roads directly connected to the city are also destroyed and the Pikachu may be forced to take a longer alternate route**.\n\n**Please also note that only friends that are waiting for a gift count as unhappy, even if they die.**\n\nSince Bash is already a legend, can you help Team Rocket this time and find out the maximum number of Bash's friends who can be made unhappy by destroying exactly one city."},{"iden":"input","content":"The first line contains three space separated integers _n_, _m_ and _s_ (2 ≤ _n_ ≤ 2·105, , 1 ≤ _s_ ≤ _n_) — the number of cities and the number of roads in the Himalayan region and the city Bash lives in.\n\nEach of the next _m_ lines contain three space-separated integers _u_, _v_ and _w_ (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_, 1 ≤ _w_ ≤ 109) denoting that there exists a road between city _u_ and city _v_ of length _w_ meters.\n\nIt is guaranteed that no road connects a city to itself and there are no two roads that connect the same pair of cities."},{"iden":"output","content":"Print a single integer, the answer to the problem."},{"iden":"examples","content":"Input\n\n4 4 3\n1 2 1\n2 3 1\n2 4 1\n3 1 1\n\nOutput\n\n2\n\nInput\n\n7 11 2\n1 2 5\n1 3 5\n2 4 2\n2 5 2\n3 6 3\n3 7 3\n4 6 2\n3 4 2\n6 7 3\n4 5 7\n4 7 7\n\nOutput\n\n4"},{"iden":"note","content":"In the first sample, on destroying the city 2, the length of shortest distance between pairs of cities (3, 2) and (3, 4) will change. Hence the answer is 2."}],"translated_statement":[{"iden":"statement","content":"一年将尽，Bash 想要给他的朋友们送礼物。喜马拉雅地区有 #cf_span[n] 座城市，它们通过 #cf_span[m] 条双向道路相连。Bash 居住在城市 #cf_span[s]。Bash 在其他每座城市中恰好有一位朋友。为了给朋友们一个惊喜，他决定给每位朋友送一只皮卡丘。*由于可能存在一些从 Bash 的城市无法到达的城市，他只向那些居住在从他的城市可达的城市中的朋友发送皮卡丘*。他还希望尽快将礼物送达。\n\n他计算出了每只皮卡丘到达目的地城市的最短时间。由于他追求完美，他告知了每位朋友礼物送达的时间。皮卡丘的移动速度为 #cf_span[1] 米/秒。朋友们听到这个消息后非常兴奋，但如果礼物延迟送达，他们会不高兴。不幸的是，火箭队正在四处活动，他们得知了 Bash 的计划。他们希望最大化让 Bash 的朋友感到不高兴的人数。\n\n他们通过恰好摧毁 #cf_span[n - 1] 座其他城市中的一座来实现这一目标。这意味着 *居住在该城市的朋友会死亡，因此他也会不高兴*。\n\n请注意，*如果一座城市被摧毁，所有与该城市直接相连的道路也会被摧毁，皮卡丘可能被迫选择更长的替代路线*。\n\n*请注意，只有那些正在等待礼物的朋友才会被算作不高兴，即使他们死亡。*\n\n由于 Bash 已经是传奇人物，你能帮助火箭队这次找出通过恰好摧毁一座城市，最多能让多少位 Bash 的朋友感到不高兴吗？\n\n第一行包含三个空格分隔的整数 #cf_span[n], #cf_span[m] 和 #cf_span[s] (#cf_span[2 ≤ n ≤ 2·105], , #cf_span[1 ≤ s ≤ n]) —— 喜马拉雅地区的城市数量、道路数量以及 Bash 居住的城市。\n\n接下来的 #cf_span[m] 行每行包含三个空格分隔的整数 #cf_span[u], #cf_span[v] 和 #cf_span[w] (#cf_span[1 ≤ u, v ≤ n], #cf_span[u ≠ v], #cf_span[1 ≤ w ≤ 109])，表示城市 #cf_span[u] 和城市 #cf_span[v] 之间有一条长度为 #cf_span[w] 米的道路。\n\n保证没有道路连接城市到自身，且不存在连接相同城市对的两条道路。\n\n输出一个整数，表示问题的答案。\n\n在第一个样例中，摧毁城市 #cf_span[2] 后，城市对 #cf_span[(3, 2)] 和 #cf_span[(3, 4)] 之间的最短距离会发生变化。因此答案是 #cf_span[2]。"},{"iden":"input","content":"第一行包含三个空格分隔的整数 #cf_span[n], #cf_span[m] 和 #cf_span[s] (#cf_span[2 ≤ n ≤ 2·105], , #cf_span[1 ≤ s ≤ n]) —— 喜马拉雅地区的城市数量、道路数量以及 Bash 居住的城市。接下来的 #cf_span[m] 行每行包含三个空格分隔的整数 #cf_span[u], #cf_span[v] 和 #cf_span[w] (#cf_span[1 ≤ u, v ≤ n], #cf_span[u ≠ v], #cf_span[1 ≤ w ≤ 109])，表示城市 #cf_span[u] 和城市 #cf_span[v] 之间有一条长度为 #cf_span[w] 米的道路。保证没有道路连接城市到自身，且不存在连接相同城市对的两条道路。"},{"iden":"output","content":"输出一个整数，表示问题的答案。"},{"iden":"examples","content":"输入\n4 4 3\n1 2 1\n2 3 1\n2 4 1\n3 1 1\n输出\n2\n\n输入\n7 11 2\n1 2 5\n1 3 5\n2 4 2\n2 5 2\n3 6 3\n3 7 3\n4 6 2\n3 4 2\n6 7 3\n4 5 7\n4 7 7\n输出\n4"},{"iden":"note","content":"在第一个样例中，摧毁城市 #cf_span[2] 后，城市对 #cf_span[(3, 2)] 和 #cf_span[(3, 4)] 之间的最短距离会发生变化。因此答案是 #cf_span[2]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, s \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 2 \\cdot 10^5 $, $ 1 \\leq s \\leq n $.  \nLet $ G = (V, E) $ be an undirected weighted graph with $ |V| = n $, $ |E| = m $, and edge weights $ w(e) \\in \\mathbb{Z}^+ $.  \nLet $ d(v) $ denote the shortest distance from city $ s $ to city $ v $ in $ G $, for $ v \\in V \\setminus \\{s\\} $.  \nLet $ R = \\{ v \\in V \\setminus \\{s\\} \\mid d(v) < \\infty \\} $ be the set of reachable cities from $ s $.  \n\n**Constraints**  \n1. $ G $ is connected or has multiple components; only vertices in the same component as $ s $ are reachable.  \n2. All edge weights are positive.  \n3. Team Rocket may destroy exactly one city $ x \\in V \\setminus \\{s\\} $.  \n4. Destroying $ x $ removes $ x $ and all incident edges.  \n\n**Objective**  \nAfter destroying one city $ x \\in V \\setminus \\{s\\} $, define:  \n- $ R' = \\{ v \\in R \\setminus \\{x\\} \\mid d'(v) < \\infty \\} $, where $ d'(v) $ is the shortest distance from $ s $ to $ v $ in $ G \\setminus \\{x\\} $.  \n- A friend in city $ v $ is *unhappy* if:  \n  - $ v = x $ (killed), or  \n  - $ v \\in R' $ and $ d'(v) > d(v) $ (gift delayed).  \n\nMaximize the total number of unhappy friends over all choices of $ x \\in V \\setminus \\{s\\} $.  \n\n**Answer**  \n$$\n\\max_{x \\in V \\setminus \\{s\\}} \\left( \\mathbb{I}_{x \\in R} + \\left| \\left\\{ v \\in R \\setminus \\{x\\} \\mid d'(v) > d(v) \\right\\} \\right| \\right)\n$$","simple_statement":null,"has_page_source":false}