Given a planar directed acyclic graph with $$$N$$$ vertices and $$$M$$$ edges. Given $$$Q$$$ queries of type $$$(a, b)$$$. For each query, output "Yes" if it's possible to reach vertex $$$b$$$ from vertex $$$a$$$ and "No" otherwise.
$$$1 \le N, M, Q \le 300000$$$.
Is it possible to solve this problem under this constraints?
Auto comment: topic has been updated by HideoSatou (previous revision, new revision, compare).
It is possible to solve reachability problem on planar dag after O(n log(n)) preprocessing. Algorithm is explained here. https://en.wikipedia.org/wiki/Reachability#Thorup's_Algorithm