#P18812. [Croatian CPC 2026]Bridovi Brljaju

[Croatian CPC 2026]Bridovi Brljaju

Bridovi Brljaju

题目描述

给定两个顶点集合均为 {1,2,…,N}\{1,2,\ldots,N\} 的无向简单图,分别称为初始图和目标图。两图都没有自环和重边。你需要通过以下操作将初始图变成目标图。

一次操作选择一个顶点 vv,以及编号变化方向:增加或减少。对于操作前存在的每条边 {v,u}\{v,u\},将其替换为 {v,w}\{v,w\},其中 ww 是将 uu 沿指定方向循环移动一个编号、并跳过 vv 后得到的编号。

编号增加时,NN 的下一个编号是 11;编号减少时,11 的上一个编号是 NN。如果移动一步到达 vv,则沿相同方向再移动一步。

所有边的替换都依据操作前的图同时进行。因为图是无向的,其他顶点与 vv 的连接关系也随之改变。不与 vv 相连的边保持不变。

更形式化地,定义循环后继 p(u)p(u) 和循环前驱 s(u)s(u):

$$p(u)=\begin{cases}u+1,&u<N,\\1,&u=N,\end{cases}\qquad s(u)=\begin{cases}u-1,&u>1,\\N,&u=1.\end{cases}$$

对于 u≠vu\ne v,定义

$$f_+(v,u)=\begin{cases}p(u),&p(u)\ne v,\\p(p(u)),&p(u)=v,\end{cases}$$$$f_-(v,u)=\begin{cases}s(u),&s(u)\ne v,\\s(s(u)),&s(u)=v.\end{cases}$$

操作 + v 将每条 {v,u}\{v,u\} 替换为 {v,f+(v,u)}\{v,f_+(v,u)\};操作 - v 将其替换为 {v,f−(v,u)}\{v,f_-(v,u)\}。

请找出一个少于 300000300000 次操作的方案,或者判断无法完成转换。不要求操作次数最少。

输入格式

第一行包含一个整数 NN(1≤N≤501\le N\le50)。

接下来 NN 行给出初始图的邻接矩阵,再接下来 NN 行给出目标图的邻接矩阵。

每行是一个长度为 NN、仅由 0 和 1 组成的字符串,不含空格。第 ii 行第 jj 列为 1 表示顶点 i,ji,j 之间有边,为 0 表示没有边。

保证两个矩阵均对称,主对角线均为 0。

输出格式

如果无法转换,输出一行 -1。

否则,第一行输出整数 KK(0≤K<3000000\le K<300000),表示操作次数。接下来 KK 行,每行输出 + v 或 - v,其中 1≤v≤N1\le v\le N。

任意满足要求的操作序列均可。

样例 1

输入

4
0101
1000
0001
1010
0011
0001
1000
1100

输出

2
- 1
+ 4

样例 2

输入

2
01
10
00
00

输出

-1

样例 3

输入

1
0
0

输出

0

样例解释

样例 1 中,执行 - 1 时,边 {1,2}\{1,2\} 和 {1,4}\{1,4\} 同时变为 {1,4}\{1,4\} 和 {1,3}\{1,3\}。此时图中的边为 {1,3}\{1,3\}、{1,4}\{1,4\}、{3,4}\{3,4\}。

随后执行 + 4,边 {1,4}\{1,4\} 和 {3,4}\{3,4\} 同时变为 {2,4}\{2,4\} 和 {1,4}\{1,4\},得到目标图。

样例 2 无法完成转换。样例 3 的初始图已经等于目标图。