题目描述

一个关于三叉树的题目，小于 $100$ 的值代表树叶，大于 $100$ 的值为分支点，建树的过程是水平方向建树。先输入 $n$，代表有 $n$ 组数据，接下来 $n$ 行，输入 $4$ 个数，第一个数代表根节点，接下来分别代表三个子节点，$-1$ 代表子节点不存在，输入的顺序按照层次遍历的次序。接下来，要求寻找叶子节点的最短路径，最短路径是指不经过重复的边。输入方式，首先输入一个值 $m$，代表 $m$ 行，接下来 $m$ 行输入 $m$ 个叶子节点和对应的优先级，要求按优先级输出从上次到达的位置到该节点的最短路径，每条路径的最后一个节点要求输出目标叶子节点，最后要求回到根节点。

输入格式

第一行输入一个正整数 $n$，表示用于建树的层次遍历描述共有 $n$ 组。