题目描述

建立一个双向链表，使程序可以删除链表中val为x的节点。

题目保证被删除的节点有且只有一个。

输入格式

共n+2行。

第一行一个整数n（1≤n≤10000)，表示节点个数。

接下来n行，每行三个整数，分别表示每个节点存储的值、上个节点的编号（若为-1表示没有上一个节点）和下个节点的编号（若为-1表示没有下一个节点），头节点编号为1，尾节点编号为2。

第n+2行一个整数x为需要删除的值为x的节点。

输出格式

共2行。

第一行为删除val为x节点后，从左往右的各节点的值。

第二行为删除val为x节点后，从右往左的各节点的值。

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

3 5 1
1 5 3

数据规模与约定

对于 $60\%$ 的数据，$0\lt a,b \le 100$；
对于 $100\%$ 的数据，$0\lt a,b \le 10^9$。