rt，裸 bfs 暴力卡卡常过了。

$O(qn^4)$ 好像确实能过。