{"problem":{"name":"Many Lamps","description":{"content":"There is a simple graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertices $u_i$ and $v_i$.   Each vertex has one lamp on it. Initially, all the lamps ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc345_f"},"statements":[{"statement_type":"Markdown","content":"There is a simple graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertices $u_i$ and $v_i$.  \nEach vertex has one lamp on it. Initially, all the lamps are off.\nDetermine whether it is possible to turn exactly $K$ lamps on by performing the following operation between $0$ and $M$ times, inclusive.\n\n*   Choose one edge. Let $u$ and $v$ be the endpoints of the edge. Toggle the states of the lamps on $u$ and $v$. That is, if the lamp is on, turn it off, and vice versa.\n\nIf it is possible to turn exactly $K$ lamps on, print a sequence of operations that achieves this state.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min\\left( 2 \\times 10^5, \\frac{N(N-1)}{2} \\right)$\n*   $0 \\leq K \\leq N$\n*   $1 \\leq u_i < v_i \\leq N$\n*   The given graph is simple.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc345_f","tags":[],"sample_group":[["5 5 4\n1 2\n1 3\n2 4\n3 5\n1 5","Yes\n3\n3 4 5\n\nIf we operate according to the sample output, it will go as follows:\n\n*   Choose edge $3$. Turn on the lamps on vertex $2$ and vertex $4$.\n*   Choose edge $4$. Turn on the lamps on vertex $3$ and vertex $5$.\n*   Choose edge $5$. Turn on the lamp on vertex $1$ and turn off the lamp on vertex $5$.\n\nAfter completing all operations, the lamps on vertices $1$, $2$, $3$, and $4$ are on. Therefore, this sequence of operations satisfies the conditions.\nOther possible sequences of operations that satisfy the conditions include $X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1)$. (It is allowed to choose the same edge more than once.)"],["5 5 5\n1 2\n1 3\n2 4\n3 5\n1 5","No"],["10 10 6\n2 5\n2 6\n3 5\n3 8\n4 6\n4 8\n5 9\n6 7\n6 10\n7 9","Yes\n3\n10 9 6"]],"created_at":"2026-03-03 11:01:14"}}