{"raw_statement":[{"iden":"problem statement","content":"There is a cave.\nThe cave has $N$ rooms and $M$ passages. The rooms are numbered $1$ to $N$, and the passages are numbered $1$ to $M$. Passage $i$ connects Room $A_i$ and Room $B_i$ bidirectionally. One can travel between any two rooms by traversing passages. Room $1$ is a special room with an entrance from the outside.\nIt is dark in the cave, so we have decided to place a signpost in each room except Room $1$. The signpost in each room will point to one of the rooms directly connected to that room with a passage.\nSince it is dangerous in the cave, our objective is to satisfy the condition below for each room except Room $1$.\n\n*   If you start in that room and repeatedly move to the room indicated by the signpost in the room you are in, you will reach Room $1$ after traversing the minimum number of passages possible.\n\nDetermine whether there is a way to place signposts satisfying our objective, and print one such way if it exists."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N\\ (1 \\leq i \\leq M)$\n*   $A_i \\neq B_i\\ (1 \\leq i \\leq M)$\n*   One can travel between any two rooms by traversing passages."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$:$\n$A_M$ $B_M$"},{"iden":"sample input 1","content":"4 4\n1 2\n2 3\n3 4\n4 2"},{"iden":"sample output 1","content":"Yes\n1\n2\n2\n\nIf we place the signposts as described in the sample output, the following happens:\n\n*   Starting in Room $2$, you will reach Room $1$ after traversing one passage: $(2) \\to 1$. This is the minimum number of passages possible.\n*   Starting in Room $3$, you will reach Room $1$ after traversing two passages: $(3) \\to 2 \\to 1$. This is the minimum number of passages possible.\n*   Starting in Room $4$, you will reach Room $1$ after traversing two passages: $(4) \\to 2 \\to 1$. This is the minimum number of passages possible.\n\nThus, the objective is satisfied."},{"iden":"sample input 2","content":"6 9\n3 4\n6 1\n2 4\n5 3\n4 6\n1 5\n6 2\n4 5\n5 6"},{"iden":"sample output 2","content":"Yes\n6\n5\n5\n1\n1\n\nIf there are multiple solutions, any of them will be accepted."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}