题目描述

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

小 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 一个带标号的“好的”无向图即可。如果有多种方案，输出任意一种即可。

输入格式

一行一个正整数表示 $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$ 的所有可能中本质不同的合法状态数最大的。

数据范围与提示