Many Lamps

AtCoder

IDabc345_f

Time2000ms

Memory256MB

Difficulty—

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 are off. Determine whether it is possible to turn exactly $K$ lamps on by performing the following operation between $0$ and $M$ times, inclusive. * 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. If it is possible to turn exactly $K$ lamps on, print a sequence of operations that achieves this state. ## Constraints * $1 \leq N \leq 2 \times 10^5$ * $0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)$ * $0 \leq K \leq N$ * $1 \leq u_i < v_i \leq N$ * The given graph is simple. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ [samples]

Samples

Input #1

Output #1

Yes
3
3 4 5

If we operate according to the sample output, it will go as follows:

*   Choose edge $3$. Turn on the lamps on vertex $2$ and vertex $4$.
*   Choose edge $4$. Turn on the lamps on vertex $3$ and vertex $5$.
*   Choose edge $5$. Turn on the lamp on vertex $1$ and turn off the lamp on vertex $5$.

After completing all operations, the lamps on vertices $1$, $2$, $3$, and $4$ are on. Therefore, this sequence of operations satisfies the conditions.
Other 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.)

Input #2

Output #2

No

Input #3

Output #3

Yes
3
10 9 6

API Response (JSON)

{
  "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments