UOJ Logo Universal Online Judge

UOJ

#75. 【UR #6】智商锁

统计

当你自信满满地把你认为的正确密码输入后,时光机滴滴报警 —— 密码错误。你摊坐在了地上。

黑衣人满意地拍了拍你的肩膀:“小伙子,不错嘛。虽然没解开密码,但是离解开密码也不远咯。其实刚才是个对你的考验。来加入我们保护星期日委员会吧!”

你惊讶得从地上直接 splay 了起来:“就是那个传说中的保护星期日委员会?咦,那为什么今天星期日还要上学呢?”

黑衣人:“你不是高三学生吗?”,你一脸无语。黑衣人又说道:“小伙子跟我干吧,我们一起去摧毁 IIIS。”

于是你们跋山涉水来到了 IIIS 基地的一个秘密仓库门前。duang地一下放倒了门卫之后你们试图开门窃取秘密资料。可是这个门装备了最新的智商锁,只有你的智商恰好等于锁的主人门才会打开。于是门上出现一道迷题:

给你一个 $k$,请你构造一个结点数不超过 $100$ 的无向图,使得这个无向图中生成树的个数对 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)取模后恰为 $k$。

作为智商超高的你一定一眼秒掉了此题!请写一个程序证明你的智商跟智商锁的主人一样吧!

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行每行一个非负整数 $k$,保证 $0 \leq k < 998244353$。

输出格式

你需要对每一个给出来的 $k$,输出一张无自环无重边的无向图。如果有多解输出任意一组解均可。如果无解请输出卖萌表情 “QwQ”(不含引号)。

输出无向图时,先一行两个非负整数 $n, m$,分别表示结点数和边数。你需要满足 $1 \leq n \leq 100$。接下来 $m$ 行,每行两个整数 $v, u$ 表示 $v$ 号结点和 $u$ 号结点之间有一条无向边。结点从 $1$ 到 $n$ 编号。

样例一

input

2
8
16

output

4 5
1 2
1 4
2 4
2 3
3 4
4 6
1 2
1 4
2 4
2 3
3 4
1 3

explanation

样例输出的两个图分别如下:

1---4     1---4
|  /|     |\ /|
| / |     | x |
|/  |     |/ \|
2---3     2---3

左图中,2 到 4 这条边在生成树上有 $4$ 种方案,不在生成树上又有 $4$ 种方案。所以共有 $8$ 棵生成树。

右图有 $16$ 棵生成树。

样例二

见样例数据下载。

限制与约定

对于所有数据,$T \leq 10$。

测试点编号 $k$ 其它限制
1$k \leq 100$ 且 $k \neq 2$
2
3$k \lt 998244353$保证存在 $n \leq 6$ 的图满足题意
4
5$k = 3, 16, 125, 1296, 16807, 262144, 4782969$
6$k = 229805564, 305655011, 988403481, 987167444, 826614133$
7$k = 110, 221, 667, 1457, 2021$
8$k \lt 998244353$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载