Minimum Sequence Spanning Tree

题号：NC217567
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given a tree with $n$ vertices numbered from 1 to $n$ , we say a sequence $a_1, a_2, \cdots, a_n$ is a "spanning sequence" of the tree if it passes the following validation:

Paint all the vertices white at the beginning;
Select vertex $a_1$ as the root and paint it black. Now the tree becomes a rooted tree and each vertex except $a_1$ has a parent;
Enumerate $i$ from 2 to $n$ . If the parent of vertex $a_i$ is black, also paint vertex $a_i$ black, otherwise do nothing;
If all the vertices turn black, sequence $a_1, a_2, \cdots, a_n$ is a spanning sequence of the tree.

It's obvious that the spanning sequence of a given tree is not unique. For example, for the tree shown below, both {2, 1, 5, 3, 4} and {1, 2, 3, 4, 5} are its spanning sequences.

We now present you with a connected graph with $n$ vertices and $m$ edges. Please find a spanning tree of this graph such that the minimum spanning sequence of the tree is as large as possible. In this problem, we compare the sequences by lexicographic order.

In case you're not familiar with some concepts referred above:

A tree is a connected graph with $n$ vertices and $(n-1)$ edges.
A spanning tree of a graph is a sub-graph of the original graph such that it contains all the vertices of the original graph and is a tree.
Sequence $x_1, x_2, \cdots, x_n$ is lexicographically smaller than sequence $y_1, y_2, \cdots, y_n$ if there exists an integer $k$ such that $1 \le k \le n$ , $x_i = y_i$ for all $1 \le i < k$ and $x_k < y_k$ .

输入描述:

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $m$ ( $2 \le n \le 10^5$ , $n - 1 \le m \le 10^5$ ), indicating the number of vertices and edges of the graph.

For the following $m$ lines, the $i$ -th line contains two integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le n$ ), indicating that there is an edge connecting vertex $u_i$ and $v_i$ .

It's guaranteed that:

- There are no self loops or multiple edges.

- The given graph is connected.

- Neither the sum of $n$ nor the sum of $m$ will exceed $5 \times 10^5$ .

输出描述:

    For each test case output one line containing  integers separated by a space, indicating the minimum spanning sequence of the desired spanning tree.

示例1

输入

复制

输出

复制

1 4 3 2
1 3 2 4