Colorful Christmas Tree

AtCoder

IDabc437_g

Time2000ms

Memory256MB

Difficulty—

The Christmas season this year is over, and it is finally time for the new year. Takahashi is busy with the big cleanup of putting away the Christmas tree. There is a Christmas tree decorated with bulbs in three colors: red, blue, and green. The Christmas tree has $N$ bulbs, and they are connected by $N-1$ ribbons. When viewing the bulbs as vertices and the ribbons as edges, this graph is a tree. The bulbs are numbered from $1$ to $N$, and the ribbons are numbered from $1$ to $N-1$. Ribbon $i$ connects bulbs $u_i$ and $v_i$. Bulb $i$ is initially lit in red if $c_i$ is `R`, in green if it is `G`, and in blue if it is `B`. Takahashi is considering performing the following operation $N-1$ times to remove all ribbons. 1. Choose one ribbon among those not yet removed where the bulbs at both ends have different colors, and remove that ribbon. 2. Let bulbs $u$ and $v$ be the bulbs at both ends of the removed ribbon. For each of the bulbs $u$ and $v$, change the color they are lit in according to the following rule: * If it was lit in red, light it in green. * If it was lit in green, light it in blue. * If it was lit in blue, light it in red. Determine whether it is possible for Takahashi to remove all ribbons by repeating this operation. If possible, output one such method. You are given $T$ test cases. Solve each of them. ## Constraints * $1\leq T\leq 20000$ * $2\leq N\leq 2000$ * $c_i$ is `R`, `G`, or `B`. * $1\leq u_i,v_i\leq N$ * When viewing the bulbs as vertices and the ribbons as edges, the given graph is a tree. * $T,N,u_i,v_i$ are integers. * The sum of $N^2$ in one input file is at most $2000^2$. ## 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 is given in the following format: $N$ $c_1c_2\ldots c_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$ [samples]

Samples

Input #1

3
4
GBBR
1 2
1 3
1 4
3
RRR
1 2
2 3
5
RGBRG
1 2
2 3
3 4
3 5

Output #1

Yes
1 3 2
No
Yes
1 4 2 3

For the first test case, for example, all ribbons can be removed by performing the operations as follows:

*   Initially, the colors of the bulbs are green, blue, blue, red, in order (from bulb $1$).
*   Remove ribbon $1$. After removal, the colors of the bulbs are blue, red, blue, red, in order.
*   Remove ribbon $3$. After removal, the colors of the bulbs are red, red, blue, green, in order.
*   Remove ribbon $2$. After removal, the colors of the bulbs are green, red, red, green, in order.

The $(e_1, e_2, e_3)$ satisfying the condition are $(1, 3, 2)$ and $(2, 3, 1)$, and either one will be accepted as correct.
For the second test case, it is impossible to remove all ribbons no matter how you perform the operations.

API Response (JSON)

{
  "problem": {
    "name": "Colorful Christmas Tree",
    "description": {
      "content": "The Christmas season this year is over, and it is finally time for the new year. Takahashi is busy with the big cleanup of putting away the Christmas tree. There is a Christmas tree decorated with bul",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc437_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Christmas season this year is over, and it is finally time for the new year. Takahashi is busy with the big cleanup of putting away the Christmas tree.\nThere is a Christmas tree decorated with bul...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments