引理 1 $(n,k)$ 有解当且仅当 $(n,n-k)$ 有解。

证明 不妨设 $2k\le n$，则若 $(n,k)$ 有解显然 $(n,n-k)$ 有解。若 $(n,n-k)$ 有解，若存在 $k+1\le i\le n-k$ 使得分母上的 $i$ 的是分子上的 $j\ne i$，设分子上的 $i$ 匹配的是分母上的 $k$，则交换两对匹配 (将 $(i,j),(k,i)$ 变为 $(i,i), (k,j)$) 显然也合法。重复直到不存在满足条件的 $i$，然后将这些点都删去即得到 $(n,k)$ 的解。

引理 2 设 $2k\le n$，则有解的必要条件是 $n,n-1,\ldots,n-k+1$ 这些数中只有不超过 $1$ 个素数。

由于 $10^{18}$ 内的素数间隔不超过 $1500$，所以当 $2k\le n$ 时只有 $k\le 3000$ 可能有解，因此可以枚举 $k$ 并检验，复杂度 $O(k^2\log k)$ (边数 $O(k\log k)$，每次只需要对新加入的点进行 DFS，当然由于上界事实上更小，更劣的做法也能通过)。

输出时将中间的一大段 $0$ 二进制拆分，首尾暴力即可。