Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F2. Spanning Tree with One Fixed Degree

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an undirected unweighted connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to find any spanning tree of this graph such that the degree of the first vertex (vertex with label $$$1$$$ on it) is equal to $$$D$$$ (or say that there are no such spanning trees). Recall that the degree of a vertex is the number of edges incident to it.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$D$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}), 1 \le D < n$$$) — the number of vertices, the number of edges and required degree of the first vertex, respectively.

The following $$$m$$$ lines denote edges: edge $$$i$$$ is represented by a pair of integers $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair ($$$v_i, u_i$$$) there are no other pairs ($$$v_i, u_i$$$) or ($$$u_i, v_i$$$) in the list of edges, and for each pair $$$(v_i, u_i)$$$ the condition $$$v_i \ne u_i$$$ is satisfied.

Output

If there is no spanning tree satisfying the condition from the problem statement, print "NO" in the first line.

Otherwise print "YES" in the first line and then print $$$n-1$$$ lines describing the edges of a spanning tree such that the degree of the first vertex (vertex with label $$$1$$$ on it) is equal to $$$D$$$. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn't matter and edge $$$(v, u)$$$ is considered the same as the edge $$$(u, v)$$$).

If there are multiple possible answers, print any of them.

Examples

Input

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

Output

YES 2 1 2 3 3 4

Input

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

Output

YES 1 2 1 3 4 1

Input

4 4 3 1 2 1 4 2 3 3 4

Output

NO

Note

The picture corresponding to the first and second examples:

The picture corresponding to the third example:

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/06/2020 09:35:11 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|