Queen of Hearts, reigning over matches where victors rise and rankings trace.

图为红桃王后

现定义一种比赛方式如下：

• 参加的人一定是 $2$ 的非负整数次幂。
• 如果只有一个人参赛，那么他就是第 $1$ 名。
• 否则将选手两两匹配进行一场比赛，比赛不会有平局。所有的胜者继续通过这种比赛方式决出 $1$ 到 $2^{n-1}$ 名，败者继续通过这种比赛方式决出 $2^{n-1}+1$ 到 $2^n$ 名。

容易发现一共会进行 $n2^{n-1}$ 场比赛。

给出乱序的所有比赛的胜负关系，你需要构造出一个可能的最终排名方案或对合法的排名方案计数。保证存在至少一组合法解。

输入格式

第一行两个自然数 $type,n$。

如果 $type=0$，你应当输出一组合法解。

如果 $type=1$，你应当输出合法排名数量对 $\mathrm{998244353}$ 取模的结果。

接下来 $n\times 2^{n-1}$ 行，每行两个正整数 $u,v$，表示在某一局中 $u$ 赢了 $v$。

输出格式

如果 $type=0$，一行 $2^{n}$ 个数，第 $i$ 个数表示排名为 $i$ 的人的编号。

如果 $type=1$，一行一个数，表示合法的方案数对 $\mathrm{998244353}$ 取模的结果。

样例一

input

0 2
2 4
3 2
4 1
3 1

output

3 2 4 1

explanation

在第一轮中 $3$ 号战胜 $1$ 号，$2$ 号战胜 $4$ 号，$2,3$ 两名选手进入胜者组，$1,4$ 两名选手进入败者组。

在第二轮中胜者组中 $3$ 号战胜 $2$ 号分别获得第 $1$ 名和第 $2$ 名，败者组中 $4$ 号战胜 $1$ 号分别获得第 $3$ 名和第 $4$ 名。

最终排名为：$3$ 号，$2$ 号，$4$ 号，$1$ 号。容易发现该组数据只有这一组合法解。

样例二

input

0 3
4 8
6 1
5 7
2 4
2 6
5 3
3 6
1 7
4 1
5 2
8 7
3 8

output

5 3 2 6 4 1 8 7

explanation

该组数据共有四组合法解，另外三组分别为：

$5,3,2,6,4,8,1,7$

$5,2,3,6,4,1,8,7$

$5,2,3,6,4,8,1,7$

样例三～九

见附件下载。

限制与约定

对于所有数据，保证 $type \in\set{0,1}$，$0 \leq n \leq 18$，$1\leq u,v\leq2^n$，保证存在至少一组合法解。

时间限制：$2.5\texttt{s}$

空间限制：$512\texttt{MB}$