{"problem":{"name":".. (Double Dots)","description":{"content":"There is a cave. The 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. O","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc168_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$:$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc168_d","tags":[],"sample_group":[["4 4\n1 2\n2 3\n3 4\n4 2","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."],["6 9\n3 4\n6 1\n2 4\n5 3\n4 6\n1 5\n6 2\n4 5\n5 6","Yes\n6\n5\n5\n1\n1\n\nIf there are multiple solutions, any of them will be accepted."]],"created_at":"2026-03-03 11:01:14"}}