Background

In essence, Gensokyo is high-dimensional.

Problem Description

Cirno has caught an $n$-dimensional ant. It wants to crawl from $S(0,0,...,0)$ to $T(1,1,...,1)$.

Trapped inside this $1\times1\times...\times1$ grid, the ant can move in each step only to a point adjacent in exactly one coordinate.

Now Cirno wants to test you: what is the maximum number of pairwise vertex-disjoint paths from $S$ to $T$ (excluding $S$ and $T$) that the ant can find?

You are also required to construct such a set of paths.

Input Format

One line with one integer $n$.

Output Format

The first line contains one integer $t$, the maximum number of paths.

The next $t$ lines each contain one valid path.

A valid path is written as:

$S$ [space] $P_1$ [space] $P_2$ [space] ... [space] $T$

where $P_i$ is a binary-compressed $01$ string representing an $n$-dimensional coordinate.

Do not output extra spaces.

2

2
0 1 3
0 2 3

Hint

"This problem uses Special Judge."

Explanation of Sample 1

Path $1$: $(0,0) \rightarrow (0,1) \rightarrow (1,1)$.

Path $2$: $(0,0) \rightarrow (1,0) \rightarrow (1,1)$.

They have no common points except $S$ and $T$.

Constraints

"This problem does not use bundled testdata; the testdata has multiple difficulty levels."

For 100% of the testdata, $3 \le n \le 60$.

Attached Code Snippets

• Binary packing function

/**
 * For only cpp11, cpp14, cpp17, cpp20.
 *
 * @param: __s : The binary high-dimension position inputed.
 * @return: Standard output format( U64 ).
**/

unsigned long long zip( std::string __s ) 
  { unsigned long long __r = 0;
    for( auto __c : __s ) 
      { ( __r <<= 1ull ) |= ( __c - 0x30 ); }
    return __r; }

• SPJ code

//SPJ
#include "testlib.h"
#include<bits/stdc++.h>

typedef unsigned long long ULL;
typedef std::vector<std::string> SEQ;
typedef std::string STR;

SEQ split( std::string _par, char _sgn )
  { SEQ _rat = SEQ();
	STR _rem = STR();
	
    for( char __c : _par )
      { if( __c = _sgn ) _rat.push_back( _rem ), _rem = "";
	    else _rem += __c; }
	
	if( _rem != "" ) _rat.push_back( _rem );
	
	return _rat; }

ULL to_ULL( std::string _str ) 
  { ULL _rat = 0;
	
	for( char __c : _str )
	  { ( _rat *= 10ull ) += (ULL)( __c - '0' ); }
	
	return _rat; }

bool isPw2( ULL x )
  { return !( x & (x - 1ull) ); }

std::map<ULL, bool> MP;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
	
	ULL n = inf.readLong();
	ULL S = 0, T = (1ull << n) - 1ull;
	ULL N = ouf.readLong();
	
	if( N != n ) quitf( _wa, "Count paths wrongly." );
	
	ouf.readEoln();
	
    while( n -- ) {
    	std::string path = ouf.readLine();
    
    	ULL _lst = 0;
    	
    	for( auto N : split( path, " " ) )
    	  { ULL _now = to_ULL( N );
    		if( _now != S and _now != T and MP[_now] ) 
			  { quitf( _wa, "Paths crossing" ); }
    	    if( !isPw2( _now ^ _lst ) ) 
			  { quitf( _wa, "Wrong path format" ); }
    	    _lst = _now; MP[_now] = true; }
    	
    	if( _lst != T ) quitf( _wa, "Wrong path ending" );
	}
	
	quitf( _ok, "Accepted" );
	
    return 0;
} 

Translated by ChatGPT 5