Keep Graph Connected

AtCoder

IDarc108_c

Time2000ms

Memory256MB

Difficulty—

Given is an undirected connected graph with $N$ vertices numbered $1$ to $N$, and $M$ edges numbered $1$ to $M$. The given graph may contain multi-edges but not self loops. Each edge has an integer label between $1$ and $N$ (inclusive). Edge $i$ has a label $c_i$, and it connects Vertex $u_i$ and $v_i$ bidirectionally. Snuke will write an integer between $1$ and $N$ (inclusive) on each vertex (multiple vertices may have the same integer written on them) and then keep only the edges satisfying the condition below, removing the other edges. **Condition**: Let $x$ and $y$ be the integers written on the vertices that are the endpoints of the edge. **Exactly** one of $x$ and $y$ equals the label of the edge. We call a way of writing integers on the vertices _good_ if (and only if) the graph is still connected after removing the edges not satisfying the condition above. Determine whether a good way of writing integers exists, and present one such way if it exists. ## Constraints * $2 \leq N \leq 10^5$ * $N-1 \leq M \leq 2 \times 10^5$ * $1 \leq u_i,v_i,c_i \leq N$ * The given graph is connected and has no self-loops. ## Input Input is given from Standard Input in the following format: $N$ $M$ $u_1$ $v_1$ $c_1$ $\vdots$ $u_M$ $v_M$ $c_M$ [samples]

Samples

Input #1

Output #1

1
2
1

*   We write $1$, $2$, and $1$ on Vertex $1$, $2$, and $3$, respectively.
*   Edge $1$ connects Vertex $1$ and $2$, and its label is $1$.
    *   Only the integer written on Vertex $1$ equals the label, so this edge will not get removed.
*   Edge $2$ connects Vertex $2$ and $3$, and its label is $2$.
    *   Only the integer written on Vertex $2$ equals the label, so this edge will not be removed.
*   Edge $3$ connects Vertex $1$ and $3$, and its label is $3$.
    *   Both integers written on the vertices differ from the label, so this edge will be removed.
*   Edge $4$ connects Vertex $1$ and $3$, and its label is $1$.
    *   Both integers written on the vertices equal the label, so this edge will be removed.
*   After Edge $3$ and $4$ are removed, the graph will still be connected, so this is a good way of writing integers.

API Response (JSON)

{
  "problem": {
    "name": "Keep Graph Connected",
    "description": {
      "content": "Given is an undirected connected graph with $N$ vertices numbered $1$ to $N$, and $M$ edges numbered $1$ to $M$. The given graph may contain multi-edges but not self loops. Each edge has an integer la",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc108_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is an undirected connected graph with $N$ vertices numbered $1$ to $N$, and $M$ edges numbered $1$ to $M$. The given graph may contain multi-edges but not self loops.\nEach edge has an integer la...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments