殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲，而現在要講的，是殿壬出生後七十一個月二十二天大的故事。

殿壬這個時候已經精通各式演算法了，其中圖上的最大流問題尤其令他著迷。而在這一天，殿壬的朋友來找殿壬玩，作為天才兒童，他們決定來較量一番，比誰能比較快回答出以某兩點為源點以及匯點的最大流為多少。
遊戲的形式是這樣子的：兩人各準備了 $Q$ 個問題，每個問題都是 $(s_i,t_i)$ 這樣的形式，代表詢問以 $s_i$ 為源點、 $t_i$ 為匯點的最大流。兩人出完問題以後交換題目，誰先正確作答完全部題目的人就獲勝了！

殿壬回憶起了最大流的定義（以下以 $V$ 代表點集、 $E$ 代表邊集、邊為有向邊，亦即 $(u,v)\ne (v,u)$ ）：
對於每條邊 $(u,v)\in E$ ，令 $c(u,v)$ 為這條邊的容量，且令 $S$ 為源點， $T$ 為匯點。一個合法的流是一個函數 $f:E\to {\mathbb{R}}^{+}$ 滿足 $f(u,v)\le c(u,v),\mathrm{\forall }(u,v)\in E$ 且對於所有 $v\in V\setminus \{S,T\}$ ， ${\displaystyle \sum _{(u,v)\in E}f(u,v)=\sum _{(v,u)\in E}f(v,u)}$ 必須成立，亦即對於非源非匯的節點們，流入的流量必須等於流出的流量。一個合法的流 $f$ 的流量 $|f|$ 定義為 ${\displaystyle \sum _{(S,u)\in E}f(S,u)}$ 。一張圖上的最大流為在所有可能的流中，最大的 $|f|$ 。

殿壬還知道，如果要把以上的定義套用到無向圖上的話，只要將每條連接 $u,v$ 的無向邊看做是一條從 $u$ 到 $v$ 的有向邊以及一條 $v$ 到 $u$ 的有向邊即可。

不過要玩這個遊戲必須要有一張圖，於是殿壬又在家裡尋找了許久，終於找到了祖傳的 $N$ 點 $N$ 邊的連通無向圖，其中這張圖上的每條無向邊的容量皆為 $1$ ！於是兩人開始了比賽，可是殿壬的朋友不像殿壬那樣的擅長最大流的計算，因此請你幫幫他，回答殿壬所出的 $Q$ 道問題。

（關於網路流更詳細的說明請見下方的 Hints ，若仍不理解可以參考 day4 的網路流講義）