题目描述

给一张 $n$ 个点的竞赛图（任意两点之间恰有一条有向边）。每次旅行给定起点星球 $s$，并给出 $k$ 个不能前往的星球 $p_1,\dots,p_k$（保证 $s$ 不受影响且这些点两两不同）。

你需要规划一条不重复经过星球的路线，使得经过的星球数量最多；有些询问只需要输出最大可经过的数量。

形式化：求序列 $u_1,\dots,u_m$，满足：

• $u_1=s$；
• 对任意 $i$，$u_i\notin\{p_1,\dots,p_k\}$；
• $u_i$ 两两不同；
• 对 $1\le i<m$，存在有向边 $u_i\to u_{i+1}$；
• 最大化 $m$。

输入格式

• 第一行四个整数 $n,q_1,q_2,K$：点数、需要输出方案的询问数、不需要输出方案的询问数、子任务编号（小样例 $K=0$）。
• 接下来 $n$ 行，每行一个长为 $n$ 的 01 串：第 $i$ 行第 $j$ 列为 1 表示 $i\to j$ 有边。
• 接下来 $q_1+q_2$ 行：每行先给出 $s,k$，再给出 $k$ 个整数 $p_1,\dots,p_k$。前 $q_1$ 行需要输出方案，后 $q_2$ 行只需输出最大长度。

输出格式

输出 $q_1+q_2$ 行：

• 前 $q_1$ 行：先输出 $m$，再输出 $m$ 个整数表示经过的星球。任意一条合法且 $m$ 最大化的路线均可。
• 后 $q_2$ 行：仅输出一个数 $m$。

6 3 2 0
000010
101111
100110
100000
000100
101110
6 0
3 1 4
2 0
4 0
4 1 1

5 6 3 5 4 1
3 3 1 5
6 2 6 3 5 4 1
3
1

数据范围与提示

• 对于所有数据：$1\le n\le 2000$，$0\le q_1\le 5000$，$0\le q_2\le 10^4$，$0\le K\le 5$。