A river system is a tree of gauging stations 0 .. n-1; channels lists the n - 1 undirected connections (a, b), and the river's mouth is station root. Water flows toward the mouth, so station a is downstream of b when a lies on the path from b to the mouth (that is, a is a proper ancestor of b in the tree rooted at root).
For each query (a, b), report how a relates to b:
"same"ifa == b;"downstream"ifais a proper ancestor ofb;"upstream"ifais a proper descendant ofb;"separate"otherwise (neither lies on the other's path to the mouth).
Implement relations(n, channels, root, queries) -> list[str].
# 0 (mouth)
# / \
# 1 2
# / \
# 3 4
channels = [(0, 1), (0, 2), (1, 3), (1, 4)]
relations(5, channels, 0, [(1, 4), (4, 0), (3, 2), (2, 2)])
# ["downstream", "upstream", "separate", "same"]
Constraints: 1 <= n <= 10^5, up to 10^5 queries. The river can be a single path 10^5 stations long: recursion will overflow, and walking up the tree for every query is too slow.
Show hint
one iterative DFS gives each station entry/exit times tin/tout; a is an ancestor of b (or equal) exactly when tin[a] <= tin[b] and tout[b] <= tout[a], so each query is O(1).