# 题目

A proper vertex coloring is a labeling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most k colors is called a (proper) k-coloring.

Now you are supposed to tell if a given coloring is a proper k-coloring.

### Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N−1) of the two ends of the edge.

After the graph, a positive integer K (≤ 100) is given, which is the number of colorings you are supposed to check. Then K lines follow, each contains N colors which are represented by non-negative integers in the range of int. The i-th color is the color of the i-th vertex.

### Output Specification:

For each coloring, print in a line `k-coloring` if it is a proper `k`-coloring for some positive `k`, or `No` if not.

# 题解

## 思路

• 挺水的一题
• 给你一张图
• 给你每个点的颜色
• 让你判断是不是每个路径的两个端点颜色不同，并输出总共用了几种颜色。
• 直接把路径存储起来，然后用集合判定颜色数量即可。

## 数据结构

• 一条路由一个二元素列表组成，即两个端点
• color 是每个节点的颜色

## 算法

• 读取道路信息
• 读取颜色信息
• 遍历每条路
• 如果有一条路两个端点颜色相同，输出No，break
• 否则，输出有几种颜色。取集合取长度即可。

## 代码

• 由于使用Python可以AC，因此只放了Python的题解