时间限制： 10.0 秒 2.0 秒

空间限制： 512 MB

题目描述

区块链涉及密码学、哈希算法、拜占庭问题、共识算法、故障模型、网络模型等诸多知识，也在金融等领域有广泛的应用。本题中，我们需要实现一个简单的区块链系统。

在一个分布式网络中，有 $n$ 个节点通过 $m$ 条边相连，节点编号从 $1$ 至 $n$。每个节点初始化都有一个相同的“创世块”，链长都为 $1$。每个节点在整个过程中都需要维护一条主链，任何操作都只在主链上进行。在整个系统中产生的每个新块都有唯一的整数编号，创始块的编号为 $0$，其余块的编号都为正整数。当某个节点的链更新时，会将它的主链发送给它相邻的节点（邻居）；而当节点收到链时，决定是否更新自己的主链。下列情况可能会导致某个节点的链更新：

• 某个节点接收到邻居发送过来的链，与当前自己的主链进行比较：
  • 如果接收到的链更长，则将其作为自己的主链；
  • 如果收到的链长度与自身主链相同，且最后一块编号更小，则将其作为自己的主链
  • 如果接收到的链更短，则直接忽略该链。
• 某个节点产生一个新块，将新块放在主链的尾部。

假设网络带宽足够大，每个节点状态更新后，会立刻将自己的主链同时发送给所有邻居。每个节点在每个时刻总是先接收链，再产生新块（注意这与实际的区块链工作方式不相同）。每个节点发送、接收、产生块不消耗时间，只有在网络中传输链会消耗时间。不过因为一些故障，这个网络可能会出现“分区”的情况，即出现多个子网络，不同子网络的节点无法互相收发消息。

在计算机中常用逻辑时钟来定义“时刻”。逻辑时钟初始时间为 $0$，以单位 $1$ 递增。任意节点传输一条链到其邻居所花费的时间相同，都为 $t$。现在已知整个网络的结构以及每个节点产生新块的时间，需要查询特定时刻某个节点的主链。

输入格式

从标准输入读入数据。

保证题中所有输入均为整数，并且所有整数绝对值不大于 $10^9$。

第一行两个正整数分别为 $n, m$，分别表示网络的 $n$ 个节点和 $m$ 条边。

接下来 $m$ 行，每行 $2$ 个正整数 $u_i, v_i\ (1 \leq i \leq m)$，表示网络中节点 $u_i$ 和节点 $v_i$ 具有（双向）连接。保证网络中没有重复连接，但是可能会有 $u_i=v_i$ 的连接。

接下来一行两个正整数 $t, k$，分别表示每次传输延时 $t$ 和操作（产生块或查询）的数量。

接下来 $k$ 行，每行 $2$ 或 $3$ 个正整数：

• 如果是三个数 $a_i, b_i, c_i$，表示节点 $a_i$ 在 $b_i$ 时刻产生了一个编号为 $c_i$ 的块。
• 如果是两个数 $a_i, b_i$，表示查询节点 $a_i$ 处理完 $b_i$ 时刻及以前的所有操作后的主链。保证对于同一时刻，任何查询在输入文件中都出现在当前时刻所有的新块被产生之后。
• 保证所有操作的 $b_i \leq b_{i+1}\ (1 \leq i < k)$，所有产生块操作的 $c_i$ 互不相同。

输出格式

输出到标准输出。

依次输出若干行，分别对应每一次查询。

每行第一个正整数 $L$ 表示主链的长度，接下来 $L$ 个数表示主链每个块的编号。从链头（一定为 $0$）到链尾依次输出。

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 27
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 10 10
2 11 9
1 11
2 11
3 11
4 11
5 11
1 12
2 12
3 12
4 12
5 12

2 0 1
2 0 2
2 0 3
2 0 4
2 0 5
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
3 0 1 10
4 0 1 10 9
3 0 1 10
3 0 1 10
3 0 1 10
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9
4 0 1 10 9

样例 1 解释

网络中的节点与连接关系形成一张完全图。在时刻 $1$ 时，所有节点都产生一个块，所以查询结果主链长度都为 $2$。主链更新后，将自己的主链发给所有邻居。

因为传输时间为 $1$，所以在时刻 $2$ 时，所有节点都收到其他节点发来的主链并更新，更新后发送新的主链给邻居。此时查询所有节点，主链都为 $0 1$。

节点 $1$ 在时刻 $10$ 产生了新的块 $10$，并发送给邻居。所有邻居在时刻 $11$ 时接收到节点 $1$ 发送的块 $10$。同时，节点 $2$ 在时刻 $11$ 产生了新块 $11$。所以，时刻 $11$ 时的节点 $2$ 主链长为 $4$，其余节点主链长为 $3$。所有发生更新的节点在时刻 $11$ 时向邻居发送自己的主链。

所以在时刻 $12$ 时，所有节点的主链长为 $4$。

15 13
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 9
1 10
10 11
11 12
12 13
14 15
6 28
1 1 1
1 2 2
1 6
2 7
13 7
9 7
5 7
3 14
8 14
5 14
11 14
9 25
5 25
13 25
9 29 3
5 29 4
13 29 5
1 53
2 59 6
2 59
1 1000
3 1000
8 1000
9 1000
10 1000
13 1000
14 1000
15 1000

3 0 1 2
2 0 1
1 0
1 0
1 0
3 0 1 2
1 0
1 0
3 0 1 2
2 0 1
2 0 1
2 0 1
4 0 1 2 3
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
5 0 1 2 3 6
1 0
1 0

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

在本评测链接中，保证所有数据的输出量不超过 10 MiB。