题目背景

（注：题面较长，如果不想读题可以直接看后面的题目描述，不过题目背景部分对理解题意有一定帮助)

小C是一名菜鸡OIer。这天，小C在一次NOIP模拟赛中看到了这样一道题目：

对于一张n个点m条边的无向图，如果它的节点标号从1到n，且无重边自环，还没有孤点，那么称它是“好的”。对于“好的”无向图，定义这张图的变换为一张m个点的有向图，构造过程如下：
    1.将有向图的点与无向图的边以某种方式一一对应。
    2.对于无向图中每个点，将这个点在无向图中的出边按照终点从小到大排序，然后把这些边在有向图中对应的点按顺序连成一条链。
给定一张有向图G，已知G是由一张“好的”无向图变换得到的。现在需要给G中每个点分配一个正整数对(u,v)，使得把这些(u,v)看成u到v的边之后，连成的无向图是“好的”，并且将连成的无向图变换之后，得到的有向图与G完全重合。此处的完全重合是指，在上述变换的步骤1，将G中的每个点与它在无向图中形成的边对应，然后对无向图进行变换，就能得到G。
现在请问有多少种分配数对的方式呢，由于答案可能很大，你只需要输出答案对998244353取模的值。

小C看到混乱的题面，没有理解题目的意思，因此他去看了一下下面的这个样例解释：

样例输入：
    3 2
    1 2
    1 3
样例输出：
    6
样例解释：
    下面6张图就是6种方案的无向图，每条边上面的数字代表这条边所对应的G中节点编号。

其中第一张图的变换过程如下：

可以看出G中1,2,3号点的分配数对是(1,2),(1,3)及(2,4)。

然而当小C还沉浸在终于明白题目的喜悦之中时，他发现他的神仙同学们已经开始敲键盘了。小C很慌张，他看了一眼数据范围，$n\leq 400$，由于机房的电脑非常厉害，这个数据范围明显是状压dp了。虽然小C并不会，但他会记忆化搜索，他找到了一种做法：

根据构造过程的第二步，小C按无向图标号从小到大进行搜索，每次找出一条链，满足这条链的起始点入度不为$2$，终点出度不为$2$。在这个过程中，小C将记录每个点的经过的次数，以及每一条边是否走过。小C认为两个状态本质相同，当且仅当每个点的出现次数相同而且每条边是否经过的状态也相同。

同时，小C为了减小复杂度，他会将不合法的状态排除掉，小C会对$G$中每个节点判断下面$5$个命题是否为真，如果至少有一个为真，那么他就会认为这个状态不合法，否则会认为这个状态合法：

1.这个点经过次数为$0$且它的入边和出边存在已经走过的边。

2.这个点经过次数为$2$且它的入边和出边存在还未走过的边。

3.这个点入度为$2$且这个点被走过的入边条数不等于这个点经过次数。

4.这个点出度为$2$且这个点被走过的出边条数不等于这个点经过次数。

5.这个点的出边所能到达的点经过次数最大值大于这个点经过次数。

小C使用了一种巧妙的记忆化搜索方式，使得自己的算法的时间复杂度为$O($本质不同的合法状态总数$\times n)$。他很快的实现了这个算法，去做其他的题目了。

比赛结束了，小C的同学们都使用了$O(n2^n)$的算法通过了此题，小C却TLE了，但他觉得自己的算法应该是可以通过的。他想找到使得自己算法状态数最大的$G$，但是他太菜了，于是他向你求助。每次小C会给定一个数$n$，他想让你构造一个点数等于$n$的图$G$，使得小C的算法中合法状态数最大，并告诉他最大的状态数是多少。

由于小C会使用组合数对答案进行合并，因此你需要保证将图$G$中的边看成无向边之后，图$G$是连通的，这样小C的算法才会无机可乘。

由于小C很懒，因此他希望在方案数最多的条件之下，$G$中的边数还是最少的。

由于图$G$已知是由“好的”无向图变换而成，因此你只需要给小C一个带标号的“好的”无向图即可。如果有多种方案，输出任意一种即可。

题目描述

对于一张$n$个点，$m$条边，有标号，无自环无重边无孤点的无向图，定义它的变换是构造方式如下的有向图：

1.有向图有$m$个点，与无向图$m$条边一一对应。

2.对于无向图中每个点，将与它相连的边按照另一个端点从小到大排序，按顺序将这些边在有向图中的对应点连成一条链。

定义有向图$G$的一个状态为给每个点分配$0,1,2$之一的值，给每条边分配一个$0,1$之一的值。

定义一个状态合法当且仅当对于每个点下面五个条件均不满足：

1.这个点值为$0$且它的入边和出边值不全为$0$。

2.这个点值为$2$且它的入边和出边值不全为$1$。

3.这个点入度为$2$，且这个点入边值之和不等于这个点的值。

4.这个点出度为$2$，且这个点出边值之和不等于这个点的值。

5.这个点的出边所能到达的点值不全都小于等于这个点的值。

现在请你构造一个点数为$n$的有向图$G$，满足下面几个条件：

1.$G$能被某个有标号无自环无重边无孤点的无向图变换而来。

2.$G$中的边都看成无向边之后$G$连通，即$G$是弱连通的。

3.$G$的合法状态数尽量的多。

4.在满足3的条件下，$G$的边数尽量小。

每次给定$n$，输出满足条件的任意一种图以及它的合法状态数。

输出图时只需要输出变换之前的无向图即可。

输入格式

一行一个正整数表示$G$的点数$n$。

输出格式

第一行一个正整数，表示小C的算法状态数最大值。

第二行一个正整数$n'(n'\geq 0)$表示你所输出无向图的点数。

接下来$n$行，每行两个正整数$u,v(u,v\in \{1,2,...,n'\})$表示无向图中一条连接$u,v$的边。

如果你输出的状态数最大值是正确的，且你输出了一张“好的”无向图（可能无法变换为最优的$G$），符合题目格式。你将会获得该测试点$40\%$的分数。

除去答案正确以及上面这种情况，其他的情况将会被判为答案错误。

样例输入

3

样例输出

13
4
1 2
1 3
3 4

样例解释

将三条边按顺序标号为$1,2,3$，然后进行变换，得到图$G$如下：

将边$(1,2)$，$(2,3)$分别编号为$1$,$2$，那么13种状态分别为：

1:三个点经过次数分别为$0,0,0$，未经过第一条边，未经过第二条边。

2:三个点经过次数分别为$1,0,0$，未经过第一条边，未经过第二条边。

3:三个点经过次数分别为$1,1,0$，未经过第一条边，未经过第二条边。

4:三个点经过次数分别为$1,1,0$，经过第一条边，未经过第二条边。

5:三个点经过次数分别为$2,1,0$，经过第一条边，未经过第二条边。

6:三个点经过次数分别为$1,1,1$，未经过第一条边，未经过第二条边。

7:三个点经过次数分别为$1,1,1$，经过第一条边，未经过第二条边。

8:三个点经过次数分别为$1,1,1$，未经过第一条边，经过第二条边。

9:三个点经过次数分别为$1,1,1$，经过第一条边，经过第二条边。

10:三个点经过次数分别为$2,1,1$，经过第一条边，未经过第二条边。

11:三个点经过次数分别为$2,1,1$，经过第一条边，经过第二条边。

12:三个点经过次数分别为$2,2,1$，经过第一条边，经过第二条边。

13:三个点经过次数分别为$2,2,2$，经过第一条边，经过第二条边。

可以证明，这样的图$G$状态数是点数为$3$的所有可能中本质不同的合法状态数最大的。

限制与约定

时间限制：$1s$

空间限制：$512MB$