P7155 [USACO20DEC] Spaceship P

奶牛 Bessie 外星人绑架了，现在被关在了一艘外星人的飞船里！飞船有 $N$（$1≤N≤60$）间房间，编号为 $1…N$，其中某些房间之间由单向通过的门所连接（由于使用了奇怪的外星技术，一扇门甚至可能从一间房间通回这间房间本身！）。然而，没有两扇门具有完全相同的出发和到达房间。此外，Bessie 有一个遥控器，上有编号为 $1…K$ （$1≤K≤60$）的按钮。 如果 Bessie 能够完成一个怪异的任务，外星人就会释放她。首先，他们会选择两间房间 $s$ 和 $t$（$1≤s,t≤N$），以及两个整数 $b_s$ 和 $b_t$（$1≤b_s,b_t≤K$）。他们会将 Bessie 放在房间 $s$ 内，并令她立刻按下按钮 $b_s$。然后 Bessie 需要继续在飞船内穿梭，同时按下按钮。有一些 Bessie 的行动需要遵守的规则： - 在每间房间内，在按下恰好一个按钮后，她必须选择从某扇门离开去往另一间房间（可能会回到同一间房间）或停止行动。 - 一旦 Bessie 按下某个按钮，她再次按下这个按钮即为非法，除非在此之间她按下过编号更大的按钮。换句话说，按下编号为 x 的按钮会使得这个按钮变为非法，同时所有编号 $

无

无

门连接了房间 $1→2$、$2→3$、$3→4$、$4→5$ 以及 $6→6$。 对于第一个询问，Bessie 必须在按下第一个按钮后立刻停止行动。 对于第二个询问，答案显然为零，因为无法从房间 3 前往房间 1。 对于第三个询问，Bessie 的唯一选择是从房间 1 移动到房间 2 到房间 3，同时按下按钮 1、2 和 3。 对于第四个询问，Bessie 的移动方式是唯一的，她有三种可能的按键序列： - (1,2,3,2,1) - (1,2,1,3,1) - (1,3,1,2,1) 对于最后一个询问，Bessie 有五种可能的按键序列： - (2) - (2,3,2) - (2,3,1,2) - (2,1,3,2) - (2,1,3,1,2) ### 测试点性质： - 测试点 4-7 中，$K≤5$ 且 $(b_s,s)$ 在所有询问中均相同。 - 测试点 8-11 中，对所有询问有 $b_s=K−1$ 以及 $b_t=K$。 - 测试点 12-15 中，$N,K,Q≤20$。 - 测试点 16-23 没有额外限制。 供题：Benjamin Qi