两种经典的图论算法——深度优先搜索（DFS）和广度优先搜索（BFS）——可以构建图的两棵生成树。众所周知，深度优先搜索产生的树没有横向边（即连接两个互不为祖先关系的节点的边），而广度优先搜索产生的树没有纵向边（即在树中连接一个节点与其祖先的边）。在本题中，你需要构建一棵介于两者之间的生成树，使其具有指定数量的横向边和纵向边。

回想一下，无向图由顶点集 $V$ 和边集 $E$ 组成，其中每条边连接两个顶点。我们考虑连通图，即可以通过边从任意顶点到达任何其他顶点。树是一个无环的连通无向图，而图的生成树是其边的一个子集，该子集构成一棵树，且能连通图中的所有顶点。回想树的两个基本性质：在含有 $n$ 个顶点的树中，恰好有 $n - 1$ 条边，且树中任意两个顶点之间恰好存在一条路径。

我们将在图中指定一个顶点 $r$，称其为树的根。位于从顶点 $x$ 到顶点 $r$ 的唯一路径上的顶点称为顶点 $x$ 的祖先，而该路径上的第一个顶点称为顶点 $x$ 的父节点，记作 $p_x$。根节点没有父节点。

如果图中的根和生成树已经确定，那么图中的所有边可以分为以下三种类型：

• 树边（tree edges）—— 所选生成树的边；
• 纵向边（vertical edges）—— 不属于生成树且连接一个节点与其祖先的边；
• 横向边（horizontal edges）—— 图中其余的边。

图的生成树的纵向度（verticality）定义为纵向边的数量。

给你一个含有 $n$ 个顶点和 $m$ 条边的图、树根 $r$ 以及一个整数 $h$（$0 \le h \le m - n + 1$）。你需要构建一棵以 $r$ 为根的生成树，使其纵向度等于 $h$，或者报告不存在这样的树。

输入格式

每个测试点包含多个测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^5$）—— 测试数据的组数。接下来的内容是 $t$ 组测试数据的描述。

每组测试数据的第一行包含四个整数 $n$、$m$、$r$ 和 $h$ —— 分别表示图的顶点数、边数、根节点的编号以及期望的生成树纵向度（$2 \le n \le 3 \cdot 10^5$；$n - 1 \le m \le 3 \cdot 10^5$；$1 \le r \le n$；$0 \le h \le m - n + 1$）。

接下来的 $m$ 行中，每行包含两个整数 $u_i, v_i$ —— 表示图中由一条边连接的两个顶点的编号（$1 \le u_i, v_i \le n$；$u_i \ne v_i$）。

保证所有图都是连通的，且不包含自环或重边。保证所有测试数据的 $n$ 之和不超过 $3 \cdot 10^5$。保证所有测试数据的 $m$ 之和不超过 $3 \cdot 10^5$。

输出格式

对于每组测试数据，求出满足要求的生成树 $T$。在单独的一行中输出 $n$ 个整数 $p_1, p_2, \dots, p_n$，其中 $p_i$ 是树 $T$ 中第 $i$ 个顶点的父节点编号（$1 \le p_i \le n$）。对于根节点 $p_r$，你可以输出 $1$ 到 $n$ 之间的任意整数。如果不存在满足要求的生成树 $T$，则输出 $n$ 个 $-1$。

样例

输入样例 1

4
5 7 2 0
1 2
2 3
3 4
4 1
3 5
5 4
1 5
5 7 2 1
1 2
2 3
3 4
4 1
3 5
5 4
1 5
5 7 2 2
1 2
2 3
3 4
4 1
3 5
5 4
1 5
5 7 2 3
1 2
2 3
3 4
4 1
3 5
5 4
1 5

输出样例 1

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