做法一

定义 $dp_{s,i,0/1}$ 表示当前走过的桥的状态是 $s$，最后一次路过的桥是 $i$，$0/1$ 表示最后一次过桥的方向（$u_i \rightarrow v_i$ 或者 $v_i \rightarrow u_i$）。转移时先枚举一座 $s$ 中的桥 $x$，从去掉该桥的状态中再枚举一个最后一次路过的桥 $y$，由 $dp_{s-2^x,y,0/1}$ 转移即可。

时间复杂度为：$O(n^3+m+q\cdot2^k\cdot k^2)$。

Submission #57315524 - AtCoder Beginner Contest 369

做法二

全排列枚举过桥的顺序，然后模拟即可。但大部分人都又套了一个 $O(2^k)$ 的状压，实际上没有必要。与做法一类似，记录上一次过桥的方向及答案即可做到 $O(n^3+m+q\cdot k!\cdot k)$。

Submission #57335924 - AtCoder Beginner Contest 369