AT_abc287_h [ABC287Ex] Directed Graph and Query

[problemUrl]: https://atcoder.jp/contests/abc287/tasks/abc287_h $ N $ 頂点 $ M $ 辺の有向グラフがあります。頂点には $ 1 $ から $ N $ までの番号が付いており、$ i $ 番目の有向辺は頂点 $ a_i $ から頂点 $ b_i $ へと結ばれています。 また、このグラフ上の経路について、コストを次のように定めます。 - 経路上の頂点(始点・終点を含む)の番号の最大値 $ x=1,2,\ldots,Q $ に対して次の問題を解いてください。 - 頂点 $ s_x $ から頂点 $ t_x $ への経路のコストの最小値を求めよ。ただし、そのような経路が一つも存在しない場合は代わりに `-1` と出力せよ。 なお、入力の量が多くなる場合があるので、高速な方法で入出力を行うことを推奨します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_M $ $ b_M $ $ Q $ $ s_1 $ $ t_1 $ $ \vdots $ $ s_Q $ $ t_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ x=i $ に対する出力をせよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2000 $ - $ 0\ \leq\ M\ \leq\ N(N-1) $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - $ a_i\ \neq\ b_i $ - $ i\ \neq\ j $ ならば $ (a_i,b_i)\ \neq\ (a_j,b_j) $ - $ 1\ \leq\ Q\ \leq\ 10^4 $ - $ 1\ \leq\ s_i,t_i\ \leq\ N $ - $ s_i\ \neq\ t_i $ - 入力はすべて整数 ### Sample Explanation 1 $ x=1 $ に対しては、$ 1 $ 番目の辺を通って頂点 $ 1 $ から頂点 $ 2 $ へ行く経路のコストが $ 2 $ であり、これが最小です。 $ x=2 $ に対しては、$ 2 $ 番目の辺を通って頂点 $ 2 $ から頂点 $ 3 $ へ、そして $ 3 $ 番目の辺を通って頂点 $ 3 $ から頂点 $ 1 $ へ行く経路のコストが $ 3 $ であり、これが最小です。 $ x=3 $ に対しては、頂点 $ 1 $ から頂点 $ 4 $ への経路が存在しないため `-1` と出力します。