logo AlgoBeat OnlineJudge
登录 注册

#214660. [RMI 2018] 颜色 / Colors

内存限制：512 MiB 时间限制：3000 ms 标准输入输出
题目类型：VJudge（洛谷） 评测方式：VJudge
上传者： 匿名
提交 提交记录 统计 讨论 题解

题目描述

翻译来自于 LibreOJ。

题目译自 Romanian Master of Informatics 2018 Day2 T1 「Colors」

你有一个包含 个节点和 条边的连通无向图。初始时，每个节点 有一个颜色 ，用一个介于 到 的整数表示。你可以反复修改节点的颜色，通过操作 ，其中 和 是通过边连接的节点。

给定目标颜色数组 ，你的任务是判断是否能通过上述操作将颜色数组 转换为 。

输入格式

每个输入文件包含多组测试数据，你需要分别回答每组测试数据。

第一行包含一个整数 ，表示测试数据的数量。每组测试数据的结构如下：

  • 第一行包含两个整数 和 分别表示节点数和边数。
  • 接下来一行包含 个整数 ，表示初始颜色。
  • 接下来一行包含 个整数 ，表示目标颜色。
  • 接下来的 行每行包含两个整数 ，表示节点 和 之间有一条边。

输出格式

对于每组测试数据，如果可以通过上述操作将 转换为 ，输出一行 ，否则输出 。

样例

样例输入 1

2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2

样例输出 1

1
0

数据范围与提示

样例 1 解释

在第一组测试数据中，图是一个包含 个节点和 条边的连通图。需要的操作如下：

通过这些操作，初始颜色 可以转换为目标颜色 ，因此输出 。

在第二组测试数据中，无法通过上述操作将初始颜色 转换为目标颜色 ，因此输出 。

数据范围

对于所有输入数据，满足：

  • 对于所有测试数据，，
  • 所有测试数据组的 之和 ， 之和
  • 对于所有 ，

详细子任务附加限制及分值如下表所示。

子任务 分值 附加限制
图为星形图（，一个节点连接到所有其他节点），所有测试数据的 之和
图为完全图，，所有测试数据的 之和
图为一条链（，边形成单路径），所有测试数据的 之和
图为一条链，无进一步限制
图为树，所有测试数据的 之和
图为树，初始颜色 是 的一个排列
所有测试数据的 之和
无附加限制

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium