{"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 label between $1$ and $N$ (inclusive). Edge $i$ has a label $c_i$, and it connects Vertex $u_i$ and $v_i$ bidirectionally.\nSnuke 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.\n**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.\nWe 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.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $N-1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq u_i,v_i,c_i \\leq N$\n*   The given graph is connected and has no self-loops.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$ $c_1$\n$\\vdots$\n$u_M$ $v_M$ $c_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc108_c","tags":[],"sample_group":[["3 4\n1 2 1\n2 3 2\n3 1 3\n1 3 1","1\n2\n1\n\n*   We write $1$, $2$, and $1$ on Vertex $1$, $2$, and $3$, respectively.\n*   Edge $1$ connects Vertex $1$ and $2$, and its label is $1$.\n    *   Only the integer written on Vertex $1$ equals the label, so this edge will not get removed.\n*   Edge $2$ connects Vertex $2$ and $3$, and its label is $2$.\n    *   Only the integer written on Vertex $2$ equals the label, so this edge will not be removed.\n*   Edge $3$ connects Vertex $1$ and $3$, and its label is $3$.\n    *   Both integers written on the vertices differ from the label, so this edge will be removed.\n*   Edge $4$ connects Vertex $1$ and $3$, and its label is $1$.\n    *   Both integers written on the vertices equal the label, so this edge will be removed.\n*   After Edge $3$ and $4$ are removed, the graph will still be connected, so this is a good way of writing integers."]],"created_at":"2026-03-03 11:01:13"}}