UOJ Logo

NOI.AC

#49. link

统计

题目描述

小 S 最近在玩一个策略游戏,他在里面扮演君主,调兵遣将。现在,他想把所有的军队集结起来,列成队伍。

一共有 $n$ 个可供操控的角色,用从 1 到 $n$ 的不同正整数来编号。初始时,每个角色各自形成了一个队伍(即每个队伍只有一个人)。接下来,小 S 在游戏中依次进行了 $m$ 次操作,对于第 $i$ 次操作,他会输入两个编号 $a_i, b_i$,希望编号为 $a_i$ 和 $b_i$ 的两个角色列在同一个队伍中;则系统会根据他的此次操作如下反应:

  • 如果编号为 $a_i$ 和 $b_i$ 的两个角色已经在同一个队伍中,则没有任何事情发生。
  • 否则,系统将会把这两个角色所在的队伍合成一个新的队伍,其中编号为 $a_i$ 的角色原来所在队伍中的所有角色,均排在编号为 $b_i$ 的角色原来所在队伍中的所有角色的前面,且每个队伍内部的前后关系保持不变。(即:编号为 $b_i$ 的角色原来所在队伍的队首,接在了编号为 $a_i$ 的角色原来所在队伍的队尾之后。)

$m$ 次操作依次完成后,所有的角色可能形成了一个或多个队伍。你需要按照上述规则执行这些操作,依次输出每个操作是否成功,最后输出所有人的队伍排列方式。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$。

接下来 $m$ 行,每行输入两个正整数。其中第 $i$ 行输入的两个数为 $a_i, b_i$。

每行中,相邻的两个数之间用一个空格隔开。

输出格式

输出到标准输出。

第一行输出一个长度为 $m$ 的 0/1 串,依次表示每个操作是否执行成功。如果第 $i$ 个操作执行成功(成功将两个队伍合并为一个,而非无事发生),则这个串的第 $i$ 位应当输出 1,否则应当输出 0。

接下来输出最终情况下所有的队伍。每行输出一个队伍,你需要在这一行中从队首到队尾依次输出其中所有角色的编号,且相邻的两个数之间用一个空格隔开。如果有多个队伍,则按照队伍中最小角色编号从小到大的顺序输出。

你可以参考样例来更好地理解这个输出格式。

样例

输入

7 6
6 3
2 2
2 7
7 1
1 2
7 5

输出

101101
2 7 1 5
6 3
4

解释

共有 7 个角色,6 次操作。

  • 第 1 次,成功将角色 6 和 3 连成了一个队伍;
  • 第 2 次,2 和 2 自己已经在同一队伍中,所以失败;
  • 第 3 次,成功将角色 2 和 7 连成了一个队伍;
  • 第 4 次,成功将角色 7 和 1 连成了一个队伍;
  • 第 5 次,1 和 2 已经在同一队伍中,所以失败;
  • 第 6 次,成功将角色 7 和 5 连成了一个队伍,注意此时 7 和 5 并没有直接相邻。

所以第一行输出101101

最终有 3 个队伍,其中最小的角色编号依次为 1,3 和 4,则需要按照这个顺序从小到大输出。每个队伍内部按照从队首到队尾的顺序输出。

数据规模

对于测试点 1,2,3,4,保证 $n \leq 100$。

对于测试点 3,4,5,6,7,保证 $m = n - 1$,所有的 $a_i$ 均为当时某个队伍的队尾,$b_i$ 均为当时某个队伍的队首,并且所有的操作均成功。

对于所有数据,保证 $n \leq 10^5, m \leq 10^5$。