观察到，本题 $n\le 50$，但是 $Q\le 10^5$，这就说明必然有重复的 $\{s,t\}$ 出现，这启发我们要记录答案，然后就可以极限卡过了。

（虽然但是 $956\texttt{ms}$ 那是真的极限，来一点点常数就没了，所以不建议使用 $\texttt{DFS}$）