P1700 [USACO19OPEN] Milk Factory B

The milk business is booming. Farmer John's milk factory has $N$ processing stations numbered $1 \dots N$ ($1 \le N \le 100$), and $N - 1$ passages, each connecting two processing stations. (Building passages is expensive, so Farmer John chose to use the minimum number of passages such that starting from any processing station, it was possible to reach all other processing stations.) To innovate and improve efficiency, Farmer John installed conveyor belts on each passage. Unfortunately, by the time he realized the conveyor belts were one-way, it was too late, and now each passage can only be traveled in one direction. So now it is no longer true that starting from every processing station, you can reach all other processing stations. However, Farmer John believes things may not be a complete failure, as long as there still exists at least one processing station $i$ such that starting from every other processing station, it is possible to reach processing station $i$. Note that going from any other processing station $j$ to processing station $i$ may pass through some intermediate stations between $i$ and $j$. Please help Farmer John determine whether such a processing station $i$ exists.

The first line of input contains an integer $N$, the number of processing stations. The following $N - 1$ lines each contain two space-separated integers $a_i$ and $b_i$, satisfying $1 \le a_i, b_i \le N$ and $a_i \neq b_i$. This indicates there is a conveyor belt that moves from processing station $a_i$ to processing station $b_i$, and movement is only allowed in the direction from $a_i$ to $b_i$.

If there exists a processing station $i$ such that it is reachable from every other processing station, output the smallest such $i$. Otherwise, output $-1$.

Translated by ChatGPT 5