题目描述

深度优先搜索和广度优先搜索是两种经典图算法，它们都会构造图的一棵生成树。

DFS 树有一个性质：非树边不会连接两个互相没有祖先关系的点。BFS 树则有另一个性质：非树边不会连接祖先和后代。

本题要求你构造一棵“介于二者之间”的生成树，使它有指定数量的“垂直边”。

给定一个连通无向图 $G=(V,E)$，选择一个根 $r$ 和一棵生成树后，图中的边可以分为三类：

• 树边：属于生成树的边；
• 垂直边：不属于生成树，但连接了某个点和它在树上的祖先；
• 水平边：既不是树边，也不是垂直边的其他边。

一棵生成树的垂直性定义为它的垂直边数量。

给定图、根 $r$ 和整数 $h$，请构造一棵以 $r$ 为根、垂直性恰好为 $h$ 的生成树；如果不存在，输出无解。

输入格式

第一行输入整数 $t$，表示测试数据组数。

每组数据第一行输入四个整数 $n,m,r,h$：

• $n$：点数；
• $m$：边数；
• $r$：根节点编号；
• $h$：要求的垂直性。

接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示一条无向边。

保证每个图连通，没有自环和重边。所有测试数据中 $n$ 的总和不超过 $3\cdot 10^5$，$m$ 的总和不超过 $3\cdot 10^5$。

输出格式

对每组数据，输出一行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，其中 $p_i$ 是点 $i$ 在生成树中的父亲。对于根 $r$，可以输出任意 $1$ 到 $n$ 之间的整数。

如果不存在符合条件的生成树，输出 $n$ 个 -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

一种可能输出为：

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