Not Dyed by Majority (Cubic Graph)

AtCoder

IDarc161_e

Time4000ms

Memory256MB

Difficulty—

You are given a connected simple undirected graph with $N$ vertices and $\displaystyle\frac{3}{2}N$ edges, where $N$ is a positive **even number**. The vertices are labeled from $1$ to $N$, and the $i$\-th edge connects vertex $A_i$ and vertex $B_i$. Moreover, for every vertex, the **number of incident edges is exactly $3$**. You will color each vertex of the given graph either black ( `B` ) or white ( `W` ). Here, the string obtained by arranging the colors ( `B` or `W` ) of the vertices in the order of vertex labels is called a **color sequence**. Determine whether there is a color sequence that **cannot** result from performing the following operation once when all vertices are colored, and if there is such a color sequence, find one. **Operation:** For each vertex $k = 1, 2, \dots, N$, let $C_k$ be the color that occupies the majority (more than half) of the colors of the vertices connected to $k$ by an edge. For every vertex $k$, change its color to $C_k$ simultaneously. There are $T$ test cases to solve. ## Constraints * $T \geq 1$ * $N \geq 4$ * The sum of $N$ over the test cases in each input file is at most $5 \times 10^4$. * $N$ is an **even number**. * $1 \leq A_i < B_i \leq N \ \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right)$ * $(A_i, B_i) \neq (A_j, B_j) \ \ \left(1 \leq i < j \leq \displaystyle\frac{3}{2}N\right)$ * The given graph is connected. * Each vertex $k \ (1 \leq k \leq N)$ appears **exactly $3$ times** as $A_i, B_i \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right)$. ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ Each test case $\mathrm{case}_i \ (1 \leq i \leq T)$ is in the following format: $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_{\frac{3}{2}N}$ $B_{\frac{3}{2}N}$ [samples]

Samples

Input #1

Output #1

BWWW
BWWWBWWWBB

Let us consider the first test case. For the color of vertex $1$ to be `B`, at least two of the colors of vertices $2, 3, 4$ must be `B` before the operation. Then, for at least one of the vertices $2, 3, 4$, at least two of the colors of the vertices connected to that vertex by an edge are `B`, so the color of that vertex after the operation will be `B`. Therefore, the color sequence `BWWW` cannot result from performing the operation.

API Response (JSON)

{
  "problem": {
    "name": "Not Dyed by Majority (Cubic Graph)",
    "description": {
      "content": "You are given a connected simple undirected graph with $N$ vertices and $\\displaystyle\\frac{3}{2}N$ edges, where $N$ is a positive **even number**. The vertices are labeled from $1$ to $N$, and the $i",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc161_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a connected simple undirected graph with $N$ vertices and $\\displaystyle\\frac{3}{2}N$ edges, where $N$ is a positive **even number**. The vertices are labeled from $1$ to $N$, and the $i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments