You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

初始状态已知 $n$ 个节点，分别以 $1,2,...,n$ 编号。他们以这样的链进行单向传递：

接下来会有 $m$ 次调整，每一次的调整都会是如下两种指令之一：

• $1~x$，表示将编号为 $x$ 的节点从链表中删除，他的前驱和后继互相连接；
• $2~x~y$， 表示将编号为 $y$ 的节点插入到编号为 $x$ 的节点后面，即 $x$ 连向 $y$，$y$ 向 $x$ 原来的后继进行连接。（保证 $x$ 在链且 $y$ 不在链中）

所有的指令保证合法，且不存在链中节点小于 $2$ 的情况。

现在请你输出经过 $m$ 次调整之后的链表。

输入格式

从标准输入读入数据。

输入共 $m+1$ 行.

第 $1$ 行，两个正整数 $n,m$ ，含义如题面所示。

第 $2$ 到 $m+1$ 行，每行一个指令，如题目描述所示。保证指令当中 $1\le x,y\le n$，且当前操作合法。

输出格式

输出到标准输出。

一行，表示最终的链表，每两个数用一个空格分开。

5 5
1 2
1 3
1 4
2 1 4
2 5 3

1 4 5 3

数据范围

对于 $40\%$ 的数据：$n,m\le 10^3$。

对于 $100\%$ 的数据：$n,m\le 10^6$。

提示

Chap 03 列表

看似是单向传输的链表，但是加上这些操作之后，单向链表是否还能满足要求呢？

可以实现《数据结构》当中列表的基础功能。此外，使用数组模拟，并将数组下标作为指针是一种非常便于书写的方式，后续的题目出现多个列表/平衡树/左式堆时，即可共享节点内存池。