题目描述

塔子哥有一个无向图。

包括 $n$ 个点和 $m$ 条边，请你求出这个图中以 $1$ 为根节点的广度优先遍历树，并输出每个点的父节点编号。

本题开启 Special Judge，任何满足要求的答案都会被接受。

输入格式

第一行为两个整数 $n$ 和 $m$，分别表示点和边的数量。

接下来 $m$ 行，每行两个整数 $u$ 和 $v$，表示 $u$ 和 $v$ 之间有一条连边。

$1 \le n, m \le 10^3$

$1 \le u, v \le n$

输出格式

输出 $n$ 个整数，表示每个节点的父结点编号。

7 7
1 5
3 6
2 1
6 2
5 7
4 5
3 5

0 1 5 5 1 2 5

upd 11.30：数据重造，所有提交均已重测。