The members of the LIMO-gang, who specialize in removing unwanted elements from society. From right to left: Brother Ed the Oak Processionary (because of his sophisticated methods of torture), Brother Sleep (because he only dreams about the best strategies to kill people), Brother Lampie (for his great technical skills in designing weapons), and Brother Beast (no comment).

Brother Duck is the leader of the Brotherhood of Assiduously Plundering Con-men (he is called Duck because you better duck if you ask him stupid questions like this one). Today, he has an important mission for you. He has learned that the dreaded Gangsterhood of Continuously Programming Criminals has come to Leiden! These gangsters construct brilliant master plans with sophisticated optimization algorithms, which they execute with great problem-solving skill. This time, they are after the original problem set of the very first BAPC in 1991, which is kept in Rijksmuseum Boerhaave in Leiden. Of course, brother Duck is not one of those politically correct soreheads that oppose fair robbery, but he cannot tolerate an important theft by a rival gang in his city. Hence, he has decided to initiate operation LIMO (Liquidate Interfering Mafia Overlords) for the sixth time: in this operation, the specialized unit of the brotherhood known as the LIMO-gang will give the gangsters an offer they cannot survive (i.e. kill them all). The only problem is to determine their secret hideout. That is where you come in.

Leiden can be represented as a connected undirected graph, where the museum is located at vertex 1 and the gangsters have their hideout on some different vertex. On the day of the crime, the gangsters will leave their hideout at midnight (as is their custom) and head to the museum following the shortest path (a habit of their optimizing nature). Each edge takes the same time to traverse, and from each vertex, there is a unique shortest path to the museum.

Brother Duck can install CCTV cameras at some vertices. Each camera registers whether the gangsters walk past its vertex and the time at which this happens (specified as the number of edges traversed by the gangsters from their hideout to this vertex). In particular, if a camera is installed at the gangsters' hideout or the museum, they will be registered as well. Using the cameras, Brother Duck wants to be able to deduce the location of the gangster's hideout. In particular, he wants the gangsters to be spotted by at least one camera to make sure that they have performed the crime: otherwise, the LIMO-gang might eliminate some random unrelated household, and hushing this up requires a significant amount of paperwork. Determine the minimum number of CCTV cameras needed to achieve this goal, or you may never see all your balloons again!

An optimal solution for the second sample. Brother Duck can install CCTV cameras at the blue vertices $$$1$$$ and $$$2$$$, with which he can uniquely determine the hideout of the gang. It can be proven that Brother Duck needs at least 2 cameras.