# PAT-A 真题 – 1154 Vertex Coloring

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  colors is called a (proper) -coloring.

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

### Input Specification:

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

After the graph, a positive integer  ( 100) is given, which is the number of colorings you are supposed to check. Then  lines follow, each contains  colors which are represented by non-negative integers in the range of int. The -th color is the color of the -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.

### Sample Input:

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
4
0 1 0 1 4 1 0 1 3 0
0 1 0 1 4 1 0 1 0 0
8 1 0 1 4 1 0 5 3 0
1 2 3 4 5 6 7 8 8 9

### Sample Output:

4-coloring
No
6-coloring
No

#include <bits/stdc++.h>
using namespace std;

int H(int a, int b){
if(a > b) swap(a, b);
return a * 10000 + b;
}

int main(){
vector<int> edge;
int ecnt, vcnt;
scanf("%d %d", &vcnt, &ecnt);
for(int i = 0; i < ecnt; i++){
int a, b;
scanf("%d %d", &a, &b);
edge.push_back(H(a, b));
}
int qcnt;
scanf("%d", &qcnt);
while(qcnt--){
vector<int> V(vcnt, -1);
int ccnt = 0;
unordered_map<int, bool> exist;
for(int & i : V){
int tmp;
scanf("%d", &tmp);
if(exist[tmp] == false)
ccnt++;
exist[tmp] = true;
i = tmp;
}
bool flag = true;
for(int vtx : edge){
int start = vtx % 10000, end = vtx / 10000;
if(V[start] == V[end]) flag = false;
}
if(flag) printf("%d-coloring\n", ccnt);
else printf("No\n");
}
return 0;
}