{"raw_statement":[{"iden":"statement","content":"Trans Europe Express\n\nYou're traveling on the Trans Europe Express, which consists of many train lines between cities. You want to know how many cities you can reach from a given start city, traveling only on the Trans Europe Express.\n\nFor example, if you started in City A, and the Trans Europe Express had train lines between City A and City B, City B and City C, and City D and City E, you could travel to City B or City C, but not to City D or City E.\n\nFor problems like these, you can use the graph theory algorithm Breath-First Search (BFS). The algorithm is described below in pseudocode:\n\n1. Define an empty list of cities. Add the start city to the list.\n\n2. Select the first city in the list of cities, and remove it from the list.\n\n3. Mark the selected city as visited\n\n4. For any edges that connect the selected city to another city, add the other city to the list of cities, if the city has not been visited yet\n\n5. If the list of cities is not empty, repeat steps 2-4.\n\nThen, the answer would be the number of cities that have been visited.\n\nThe first line of input contains two space-separated positive integers $n$ and $m$: the number of cities, and the number of train lines on the Trans Europe Express. The next line of input contains a single string $s$, representing the start city. The next $m$ lines contain one of the train lines of the Trans-Europe Express: two space-separated strings: the cities that the train lines connect. *The train lines can be traveled in both directions.*\n\nOutput a single integer $c$: the number of cities that you can visit by traveling only on the Trans Europe Express train lines.\n\nGiven that the pseudocode of the algorithm treats the cities as numbers rather than names, you should first map each city name to a number, before running the BFS algorithm.\n\n"},{"iden":"input","content":"The first line of input contains two space-separated positive integers $n$ and $m$: the number of cities, and the number of train lines on the Trans Europe Express. The next line of input contains a single string $s$, representing the start city. The next $m$ lines contain one of the train lines of the Trans-Europe Express: two space-separated strings: the cities that the train lines connect. *The train lines can be traveled in both directions.*"},{"iden":"output","content":"Output a single integer $c$: the number of cities that you can visit by traveling only on the Trans Europe Express train lines."},{"iden":"examples","content":"Input8 7\nDusseldorf\nDusseldorf Frankfurt\nFrankfurt Berlin\nBerlin Hamburg\nBerlin Prague\nVienna Salzburg\nSalzburg Zurich\nZurich Vienna\nOutput5\nInput3 2\nSyracuse\nSyracuse Utica\nSyracuse Rochester\nOutput3\n"},{"iden":"note","content":"Given that the pseudocode of the algorithm treats the cities as numbers rather than names, you should first map each city name to a number, before running the BFS algorithm."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cities.  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of train lines.  \nLet $ s $ be the start city (a string).  \nLet $ G = (V, E) $ be an undirected graph where:  \n- $ V $ is the set of distinct city names (vertices),  \n- $ E \\subseteq \\binom{V}{2} $ is the set of bidirectional train lines (edges).  \n\nLet $ \\phi: V \\to \\{0, 1, \\dots, n-1\\} $ be a bijection mapping city names to integer indices.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq m \\leq \\min\\left(10^5, \\binom{n}{2}\\right) $  \n3. $ s \\in V $  \n4. Each edge in $ E $ is an unordered pair of distinct city names from $ V $.  \n\n**Objective**  \nCompute the number of vertices reachable from $ s $ in $ G $ via BFS, i.e., the size of the connected component containing $ s $:  \n$$\nc = \\left| \\left\\{ v \\in V \\mid \\text{there exists a path from } s \\text{ to } v \\text{ in } G \\right\\} \\right|\n$$","simple_statement":"You are given a network of cities connected by train lines. Start from one city and find how many cities you can reach by following the train lines (you can travel in both directions). Use BFS to count all reachable cities.","has_page_source":false}