UOJ Logo Universal Online Judge

UOJ

附件下载 统计

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

洛

图为红桃王后

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

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

容易发现一共会进行 n2n1 场比赛。

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

输入格式

第一行两个自然数 type,n

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

如果 type=1,你应当输出合法排名数量对 998244353 取模的结果。

接下来 n×2n1 行,每行两个正整数 u,v,表示在某一局中 u 赢了 v

输出格式

如果 type=0,一行 2n 个数,第 i 个数表示排名为 i 的人的编号。

如果 type=1,一行一个数,表示合法的方案数对 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{0,1}0n181u,v2n,保证存在至少一组合法解。

子任务编号 type= n 分值
1 0 3 10
2 0 6 10
3 0 9 10
4 0 12 10
5 0 15 20
6 0 18 10
7 1 9 20
8 1 12 10

时间限制:2.5s

空间限制:512MB