← 返回题目列表

Codeforces · 323/B

B. 锦标赛图

中文机器翻译题面 查看原题

在这个问题中,您必须构建由 n 个顶点组成的锦标赛图,这样,对于任何有向顶点对 (v, u) (v ≠ u),都存在一条从顶点 v 到顶点 u 的路径,该路径仅包含两条边。

如果任意两个不同顶点之间(在两个可能方向中的一个)之间恰好存在一条边,则没有自循环的有向图就是一场锦标赛。

输入

第一行包含一个整数 n (3 ≤ n ≤ 1000),即图的顶点数。

输出

如果没有图表满足所描述的条件,则打印-1。

否则,打印 n 行,每行包含 n 个整数。数字应该用空格分隔。这是找到的锦标赛的邻接矩阵 a。考虑用 1 到 n 的整数对图顶点进行编号。那么,如果从 v 到 u 没有边,则 av, u = 0,如果有,则 av, u = 1。

由于输出图必须是锦标赛,因此必须满足以下等式:

- av, u + au, v = 1 对于每个 v, u (1 ≤ v, u ≤ n; v ≠ u);
- av, v = 0 对于每个 v (1 ≤ v ≤ n)。

示例

输入 #1

3

输出 #1

0 1 0
0 0 1
1 0 0

输入 #2

4

输出 #2

-1