末日塔后传(Doomsday Tower Sequel)

题目描述

末日塔 - 后传

星球上的 $n$ 座末日塔又开始释放以太能量了。

每一座末日塔释放的以太能量都有 $n$ 种类型，对于第 $k$ 种类型的以太能量，它需要通过单向管道运送到第 $k$ 座末日塔，才能被完全抑制住。

作为曾经勇闯末日塔的先锋，你被授予在任意两座末日塔之间建造一条单向管道的权力，而你的任务则是对于所有的 $i, j \in [1, n]$，当第 $i$ 座末日塔出现第 $j$ 种以太能量时，尽你所能的将其通过管道迅速运送到能够抑制这种以太能量的末日塔。

很不幸，由于以太能量过于浓密，当其被单向管道连续运输大于两次后，以太能量散发的射线将透过管道，对星球上的所有生物进行精神控制，你的任务就失败了。

请你判断存不存在能够让你任务圆满完成的管道设计方案。如果有，请输出 YES 以及任意一种设计方案；如果没有，请输出 NO。

输入格式

一个正整数 $n$ 表示星球上末日塔的数量。

输出格式

第一行一个字符串 YES 或 NO，表示是否存在圆满完成任务的设计方案。

如果为 YES，请再输出 $n$ 行 $n$ 列的邻接矩阵 $d$，$d_{i,j} = 1/0$ 表示存在/不存在从第 $i$ 座到第 $j$ 座的单向管道。

你需要保证 $d_{i,i} = 0$ 且 $\forall i \neq j, d_{i,j} \text{ xor } d_{j,i} = 1$。

样例输入 #1

3

样例输出 #1

YES
0 1 0
0 0 1
1 0 0

样例输入 #2

4

样例输出 #2

NO

数据范围

样例解释 1

$d_1$ 一次可以到 $d_2$，$d_1$先到 $d_2$，再到 $d_3$，最多利用了两个管道；$d_2$ 和 $d_3$ 同理，所以输出 YES。

样例解释 2

$n=4$ 的情况，无论你怎么建图，保证不能同时有 $d_i$ 到 $d_j$ 的往返路，这样 $d_i$ 到 $d_j$ 的连接会多于 $2$ 个管道，所以输出 NO。

数据范围

对于 $100\%$ 的数据，$n \leq 500$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接