CYCLE - Cycles, More Cycles

A m-cycle in a directed graph is defined to be a sequence of vertices v0-v1-v2-v3-...-vm where an edge (vi, vi+1) exists for each 0 <= i < n, vi != vj for all 0 <= i < j < m and vm = v0. For a given graph of n vertices we can count the number of cycles in it. Now you task is a little harder: find the maximum value among all graphs with certain constraints, that is, your graph should contain an edge from either vertex x to y or y to x, but not both.
Assume there are R m-cycles in your output, your solution will be awarded by w * R points, where w is related to n and m. Your score will be the sum of scores of all test cases. Note your source must not be larger than 10000 bytes.

Input

One line containing two blank-separated integers, n and m, where 3 <= m <= n <= 17.

Output

Adjacent matrix A of the graph you found. Numbers must be separated by spaces. Edge (i, j) exists when and only when Aij = 1. Aij + Aji <= 1 and Aii = 0 for any 0 <= i, j < n, or your solution will be judged as wrong answer.

Example

Input:
3 3

Output:
0 0 1
1 0 0
0 1 0

Assume w = 0.2, this solution will get 0.2 * 1 = 0.2 points for this case.

Added by:Tony Beta Lambda
Date:2010-08-10
Time limit:0.200s-3.400s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:Yau-awards 2008

hide comments
2011-03-29 05:49:59 Robert Gerbicz
Yes.
2011-03-29 05:49:59 Wolfram
In a cycle, must v_0, v_1, v_2, ..., v_{m-1} all be different?
2011-03-29 05:49:59 Tony Beta Lambda
Note: the author's solution is about 20 lines long and gets about 300000 points.

Last edit: 2010-08-29 08:12:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.