语言漩涡

thirtiseven 的博客

0%

acm 香港网络赛 2016 部分题解

Posted on Edited on

A A+B Problem

Given N integers in the range [−50000,50000], how many ways are there to pick three integers ai, aj, ak, such that i, j, k are pairwise distinct and ai+aj=ak? Two ways are different if their ordered triple (i,j,k) of indices are different.

Input

The first line of input consists of a single integer N (1≤N≤200000). The next line consists of N space-separated integers a1,a2,…,aN.

Output

Output an integer representing the number of ways.

Sample Input 1

1
2
4
1 2 3 4

Sample Output 1

1
4

Sample Input 2

1
2
6
1 1 3 3 4 6

Sample Output 2

1
10

题意

  从输入数据中找这样的组合 ( i , j , k ) , 使+=。输出组数。

题解

num[k]表示（ai,aj）= k的个数。然后将ai = aj的那种重复的去掉。

然后计算当a[i] = k时的（i,j,k）有多少种，很明显就是 num[ a[i]]种,

注意有一种情况是有0的时候,因为有可能会自己加了0也等于ai 。所以要统计一下0有多少个,减了0就可以了,注意(i,j)也是有顺序要求的,（i,j）和(j,i)是2个不同的,所以还要处理有0的时候要乘以2倍。 然后是因为有负数,我们要全部都加上50000变成正数就好了。

（HDU4609的变形）

思路

  1. 输入数据，保存在数组a中，输入时记录0的个数（zero）。
  2. 将每个数字出现的个数保存在num数组中，因为有负数，保存的时候+50000。
  3. 将数组a排序，a的最大值+50000就是num数组卷积之前的长度。
  4. 卷积num数组时，长度要增长为一个大于卷积之前长度*2-1的2的整数次幂。
  5. 由于涉及到复数，将num数组转化为复数数组F，num数组输入到a的最大值处（len1），增长的长度（len1到len）置为0.
  6. 计算卷积：先用FFT法求加长序列的DFT频谱（执行fft函数后的F数组），再将此时的F数组各项平方，再用IFFT求DFT频谱乘积的逆变换，便得两序列的离散线卷积。
  7. 将计算卷积之后的F数组的实部返回到num数组中。此时num[k+100000]的值为i+j=k的组数。公式是这样的 。
  8. 由于i和j不能相同，把数组a中所有元素*2对应位置的num数组卷积-1.
  9. 用数组a中的元素搜索num数组，将num数组的元素累加，并减去0个数的两倍。如果a中的元素本身是0，减去zero-1的两倍。
  10. 输出结果。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#include <iostream>
#include <cmath>   
#include <algorithm>   
using namespace std;  

const int N = 2e5+10;  
const double pi = acos(-1.0);  


struct Complex{  
	double r,i;  
	Complex(double r=0,double i=0):r(r),i(i){
		//声明复数：Complex XXX(XX,XX);
	};  
	//定义复数的加减乘运算
	Complex operator+(const Complex &rhs){  
		return Complex(r + rhs.r,i + rhs.i);  
	}  
	Complex operator-(const Complex &rhs){  
		return Complex(r - rhs.r,i - rhs.i);  
	} 

	Complex operator*(const Complex &rhs){  
		return Complex(r*rhs.r - i*rhs.i,i*rhs.r + r*rhs.i);  
	} 

};

int len;
long long a[4*N];    
Complex F[4*N];    
long long num[4*N];  //每个数字出现的个数
int n;  
long long zero = 0;   //输入值中0的个数
 

void rader(Complex F[],int len){ //len = 2^M,reverse F[i] with  F[j] j为i二进制反转   
	int j = len >> 1;  
	for(int i = 1;i < len - 1;++i){  
		if(i < j) swap(F[i],F[j]);  // reverse  
		int k = len>>1;  
		while(j>=k){  
			j -= k;  
			k >>= 1;  
		}  
		if(j < k) j += k;  
	}  
} 
//FFT  
void FFT(Complex F[],int len,int t){   
	for(int h = 2;h <= len; h <<= 1){ //分治后计算长度为h的DFT   
		Complex wn(cos(-t * 2 * pi / h) , sin( -t * 2 * pi / h)); //单位复根e^(2*PI/m)用欧拉公式展开  
		for(int j = 0;j < len;j += h){
			Complex E(1,0); //旋转因子  
			for(int k = j;k < j + h / 2; ++k){  
				Complex u = F[k];  
				Complex v = E * F[k + h / 2];  
				F[k] = u + v; //蝴蝶合并操作  
				F[k + h / 2] = u - v;  
				E = E * wn; //更新旋转因子  
			}  
		}  
	}  
	if(t == -1){   //IDFT  离散傅利叶逆变换
		for(int i = 0;i < len; ++i){
			F[i].r /= len;  
		}
	}
}  
  
//卷积   
void Conv(Complex F[],int len){  
	//用FFT法求加长序列的DFT频谱
	FFT(F,len,1);  
	//计算DFT频谱的平方
	for(long long i = 0; i < len; ++i){
		F[i] = F[i] * F[i];  
	}
	//用IFFT求DFT频谱乘积的逆变换，便得两序列的离散线卷积
	FFT(F,len,-1);  
}  
  
int main(int argc, char *argv[]){  
	//初始化 输入数据
  	cin >> n;
	memset(num,0,sizeof(num));             
	for(int i = 0; i < n; i++){    
		cin >> a[i];  
		if(a[i] == 0){
			zero++; 
		} 
		num[a[i] + 50000]++;    
	}      
	sort(a, a + n);    
	int len1 = a[n-1] + 50000 + 1; // 输入最大值+50001 
	len = 1; 
	//计算卷积后F数组长度 使len为2的整数次幂 并且 len >= 2 * len1 - 1  
	while(len < len1 * 2){
		len <<= 1;  
	}
	//num数组变为复数形式
	for(int i = 0; i < len1; i++){    
		F[i] = Complex(num[i],0);    
	}
	//初始化F数组
	for(int i = len1; i < len; i++){   
		F[i] = Complex(0,0);    
	} 
	//计算卷积 
	Conv(F,len);  
	//num数组现在是卷积后的结果，num[k+100000]的值为i+j=k的组数    
	for(int i = 0; i < len; i++){    
		num[i] = (long long)(F[i].r + 0.5); //四舍五入   
	} 	  
	//本身和本身组合是不行的,减掉取两个相同的组合  
	for(int i = 0; i < n; i++){    
		num[a[i] + a[i] + 2 * 50000]--;   
	}
	long long cnt = 0; //组数
	//找到输入在num数组中对应的位置 计算cnt 对0进行特殊处理 
	for(int i = 0; i < n; i++){    
	   if(a[i] != 0){  
		 cnt += num[a[i] + 2 * 50000];  
		 cnt -= zero * 2;  
	   }else{  
			cnt += num[a[i] + 2 * 50000];  
			cnt -= (zero - 1) * 2;  
	   }  
	}    
	cout << cnt << endl;   
	return 0;  
}

PROBLEM C

CLASSROOMS

The new semester is about to begin, and finding classrooms for orientation activities is always a headache.

There are k classrooms on campus and n proposed activities that need to be assigned a venue. Every proposed activity has specfic starting time si and ending time fi. Any such an activity should take place at one of the classrooms. Any of the k classrooms is big enough to hold any of the proposed activities, and each classroom can hold at most one activity at any time. No two proposed activities can take place at the same classroom at the same time. Even if two proposed activities overlap momentarily (the ending time of one activity equals the starting time another activity), they cannot be assigned to the same classroom.

There are so many proposed activities that there may not be enough classrooms to hold all the activities. It is desirable to have as many activities as possible. At most how many proposed activities can be assigned to the classrooms?

Input

  • The first line contains two positive integers n and k (1≤k≤n≤200000 ), representing the number of proposed activities and number of classrooms, respectively.
  • The following n lines each contains two positive integers: the ith line among these n lines contains si and fi (1≤si≤fi≤109), indicating the starting time and ending time of proposed activity i

Output

Output an integer indicating the maximum number proposed activities that can be scheduled.

Sample Input 1

1
2
3
4
5
4 2
1 4
2 9
4 7
5 8

Sample Output 1

1
3

题意

  题意，n个活动，k个教室，给定每个活动开始和结束时间，在同一个教室举行的连续两个活动结束时间和开始时间之间必须有间隔。问最多能举办多少个活动。

  贪心，把每个活动按结束时间排序，然后从头到尾扫一遍。

  multiset里存放每个教室正在进行的活动的结束时间。

  如果multiset里有某个教室的活动在活动i开始之前就结束的，活动i就可以举办，把原来的结束时间删掉，再把活动i的结束时间存进去。

  如果multiset里没有比a[i].begin小的结束时间，即当前有活动的教室在活动i开始之前都结束不了活动，此时multiset里元素的数量表示有多少个教室在同时进行活动，如果还有空教室，活动i就可以在这个教室进行，把活动i的结束时间存入multiset。

  注：实际存入multiset的是 (-a[i].ed-1),而查找时用的是（-a[i].begin）。因为要使用lower_bound函数，而lower_bound（start,end,k）返回的是集合里大于等于k的第一个数的下标，而题目里面要查找的是 比 开始时间 小的 第一个 结束时间，加个负号就刚好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <iostream>
#include <set>

#define N 200005

using namespace std;

int n , k;
struct node{
	int bg,ed;
}a[N];

bool cmp(node a , node b){        //sort-cmp
	if(a.ed== b.ed) return a.bg < b.bg;
	return a.ed< b.ed;
}

int main(){
	cin >> n >> k;
		for (int i = 0 ; i < n ; ++i)
		cin >> a[i].bg >> a[i].ed;
		sort(a,a+n,cmp);			//按照结束时间排序
		multiset<int> endtime;
        //multiset存放每个教室正在进行的活动的结束时间
		endtime.clear();
		int ans = 0;			//活动个数
		for (int i = 0 ; i < n ; i++){     //遍历每个活动
			multiset<int> :: iterator iter;   
			iter = endtime.lower_bound(-a[i].bg);  
          	//是否存在某个教室的活动在i开始时间前前就结束了
			if (iter == endtime.end()){            
       		//如果没有在活动i开始前就结束活动的教室，就另找一个教室
				if (endtime.size() < k){
					endtime.insert(-a[i].ed- 1);
					ans++;
				}
				continue;
			}
			endtime.erase(iter);                    
    		//找到了某个教室活动已经结束了，活动i在这个教室进行
			endtime.insert( - a[i].ed - 1);      
      		//更新活动的结束时间
			ans++;
		}
	cout << ans << endl;
	return 0;
}

Problem D

Curious Cupid

There are K different languages in the world. Each person speaks one and only one language. There are exactly N single men and N single women.

Cupid, the god of love, wants to match every single man to a single woman, and vice versa. Everybody wants to find a partner who speaks the same language as s/he does. Communication between the couple is very important! Cupid asks these N men to stand in a line, and likewise for the N women. Cupid knows that the ith man speaks language ai and the ith woman speaks language bi.

It is too hard for Cupid to match all people at the same time. What Cupid does is to repeatedly look at some specific interval in these two lines, pick the men and women in that interval and find the maximum number of man-woman pairs who speak the same language and can be matched.

Input

  • The first line contains three integers N, M and K (1≤N≤50000,1≤M≤50000,1≤K≤1000000).
  • The second line contains N integers a0,a1,a2,…,aN−1, where ai (0≤ai<K) is the language spoken by the ith man.
  • The third line contains N integers b0,b1,b2,…,bN−1, where bi (0≤bi<K) is the language spoken by the ith woman.
  • In the next M lines, each line contains two integers L and R (0≤L≤R<N), representing the starting and ending index of the interval. That is, Cupid is looking at men L,L+1,…,R and women L,L+1,…,R.

Output

For each interval, print the maximum number of couples Cupid could match.

Sample Input 1

1
2
3
4
5
6
7
3 4 2
0 0 1
0 0 0
0 0
2 2
0 1
1 2

Sample output 1

1
2
3
4
1
0
2
1

莫队算法描述

这里和这里还有这里是一些资料。我个人的理解是这样的，给你一堆查询区间，如果q(l,r)可以用q(l+/-n)(r+/-m)以O(n)复杂度推出来，就可以用莫队算法，所以实际上求的是每个(l,r)点的最小曼哈顿距离树，莫队算法的处理是将这些点分块排序，改变了查询的顺序，从而降低算法复杂度。具体见上面的链接和代码注释。

题意

给你两串数，一串代表男的，一串代表女的，每个数代表这个人说的语言，现在要给一个区间[L,R]里面的人配对，只有语言相同的才能配一对，问对于每个区间，最多能配成几对。莫队算法处理。

N：男人和女人的个数

M：查询次数

K：语言总数

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define N 51000
#define K 1000100

int n, m, k;
int a[N], b[N], pos[N], c[2][K], ans[N], cnt;

struct node {
	int l, r, id;
	void sc(int i){
		scanf("%d%d", &l, &r);
		id = i;    						//id 查询的顺序编号
	}									
}p[N];   								// p数组存储查询
										
bool cmp(node a, node b) {   			// 排序 块的顺序为第一关键字，r为第二关键字
	if(pos[a.l] == pos[b.l]) 
		return a.r < b.r;
	return pos[a.l] < pos[b.l];
}

void update(int x, int y) {  
  //每次update的时候更新某种语言人数，取男女中的较小值更新到答案中
	if(a[x] != b[x])     
  //男人女人语言不一样 cnt减去男人和女人说a[x]语言的最小值和男人和女人说b[x]语言的最小值
		cnt -= min(c[0][a[x]], c[1][a[x]]) + min(c[0][b[x]], c[1][b[x]]); 
	else 				 //男人女人语言一样 cnt减去男人和女人说a[x]语言的最小值
		cnt -= min(c[0][a[x]], c[1][a[x]]);
	c[0][a[x]] += y;	//更新语言数量
	c[1][b[x]] += y;
	if(a[x] != b[x]) 	//然后再加回去
		cnt += min(c[0][a[x]], c[1][a[x]]) + min(c[0][b[x]], c[1][b[x]]);
	else 
		cnt += min(c[0][a[x]], c[1][a[x]]);
}

/*
void pri() {  //输出数组c 测试用函数
	for(int j = 0;j < 2;j++)
		for(int i = 0;i < n;i++)
			printf("%d%c", c[j][i], " \n"[i==n-1]);
}
*/

void solve() {
	memset(c, 0, sizeof(c));//c数组 0男人 1女人 c[0/1][x]为该性别说x语言的人的数量
	int pl = 0, pr = 0;									
	cnt = a[0] == b[0] ? 1 : 0;	
  //cnt 计数变量 如果第0个男人和第0个女人说的语言相同 cnt为1 否则为0
	c[0][a[0]]++; 						//说a[0] b[0]语言的男人和女人数量 + 1
	c[1][b[0]]++;										
	for(int i = 0;i < m;i++) {							//对查询次数遍历
		int id = p[i].id, l = p[i].l, r = p[i].r;		
      //第i次查询的id l r（此时p数组已经排序，排序方法见cmp
		for(int j = pr + 1;j <= r;j++)		//从pr和pl开始O(1)的推到r和l的查询次数
			update(j, 1);
		for(int j = pr;j > r;j--)
			update(j, -1);
		for(int j = pl;j < l;j++)
			update(j, -1);
		for(int j = pl-1; j >= l;j--)
			update(j, 1);
		pr = r; pl = l;						//然后把开始的那个点更新为这个点
		ans[id] = cnt;						//记录ans的cnt
	}
	for(int i = 0;i < m;i++)				//以输入的顺序输出答案
		printf("%d\n", ans[i]);
}

int main() {
	while(~scanf("%d%d%d", &n, &m, &k)) {  	
      //输入n 男人和女人的个数 m 查询次数 k 语言总数
		for(int i = 0;i < n;i++)			//数组a[i] 第i个男人说的语言
			scanf("%d", &a[i]);				
		for(int i = 0;i < n;i++)   			//数组b[i] 第i个女人说的语言
			scanf("%d", &b[i]);				
		int bk = sqrt(n + 1.0);				// bk 分块的块数
		for(int i = 0;i < n;i++)			
			pos[i] = i / bk;				// pos[i] 第i组 ？？ 被分到第pos[i]块
		for(int i = 0;i < m;i++)			
			p[i].sc(i);						//输入查询 保存在node数组 p[i] 中
		sort(p, p+m, cmp);					//为p排序
		solve();							
	}										
	return 0;								
}

Problem F

Crazy Driver

In the Linear City, there are N gates arranged in a straight line. The gates are labelled from 1 to N. Between adjacent gates, there is a bidirectional road. Each road takes one hour to travel and has a toll fee. Since the roads are narrow, you can only travel from gates to gates but cannot U-turn between gates.

Crazy driver Gary starts at Gate 1 at time 0 and he wants to drive through Gate N while minimizing the cost of travelling. However, Gate i only allows a car to pass through after a certain time Ti. As Gary is crazy, his car will always be traveling on any one of the roads, i.e., it will not stop at a gate. What is the minimum cost for him to drive through Gate N ?

As an example, consider the sample input below. An optimal solution is the following:

  • Gate 1 to Gate 2 (cost 5)
  • Gate 2 to Gate 1 (cost 5)
  • Gate 1 to Gate 2 to Gate 3 (cost 9)
  • Go between Gate 3 and Gate 4 until 7-th hour (cost 6)
  • Go to and pass through Gate 5(cost 8)

Input

The first line contains an integer, N(2≤N≤105), the number of gates. The second line has N−1 integers, C1,…,CN−1. Ci (1≤Ci≤106) represents the toll fee of the road between Gate i and Gate i+1. The third line has N integers, T1,…,TN. Ti (0≤Ti≤106) represents the opening time (in hour) for each gate. T1 will always be 0.

Output

Output an integer representing the minimum cost of traveling.

Sample Input 1

1
2
3
5
5 4 2 8
0 2 4 4 8

Sample output 1

1
33

题意

题意：n个门编号1~n,从门i到i+1有一条双向通路，每条路花费的时间都是1小时，每条路花的路费分别是Ci, 每个门开的时刻分别是Ti，一个司机从门1开到门n，中间不停车，即如果到达门i的时候门没开就必须往返于前面的路上直到门开的时刻，问到门n最少花多少路费。

记录每扇门之前的路的最小路费，通过每个站点，不足的时间在之前花费最少的路上跑来回，答案就出来了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <algorithm>
#include <cstring>
#include <string.h>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <cstdio>
#include <cmath>

#define LL long long
#define N 100005
#define INF 0x3ffffff

using namespace std;

int n;
int c[N];               //门i-1到门i的路费是Ci
int m[N];             //门i之前的路的路费最小值
int t[N];               //每个门开的时刻

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++) {
        scanf("%d",&c[i]);
        if(i==1) m[i]=c[i];
        else m[i]=min(m[i-1],c[i]);
    }
      for(int i=0;i<n;i++) {
          scanf("%d",&t[i]);
      }

    int tt=0;           //当前时刻
    int i=0;
    long long ret=0;
    while(i<n)
        {
            i++;
            tt++;
            ret+=(long long)(c[i]);
            int tmp=t[i]-tt;                   //离门开还有多久

            while(tmp>0){
                tmp-=2;
                ret+=(long long)(m[i]*2);
                tt+=2;
            }
        }
        cout<<ret<<endl;
    return 0;
}

Problem G

k-Colouring of a Graph

You are given a simple graph with N nodes and M edges. The graph has the special property that any connected component of size s contains no more than s+2 edges. You are also given two integers k and P. Find the number of k-colourings of the graph, modulo P.

Recall that a simple graph is an undirected graph with no self loops and no repeated edges. A k-colouring of a graph is a way to assign to each node of the graph exactly one of k colours, such that if edge (u,v) is present in the graph, then u and v receive different colors.

Input

The first line of input consists of four integers, N,M,k, and P (1≤N≤50000, 0≤M≤1.5N, 1≤k≤109, 1≤P≤2⋅109). The next M lines of input each contains a pair of integers A and B (1≤A≤N, 1≤B≤N), describing an edge in the graph connecting nodes A and B.

Output

Output the number of k-colourings of the given graph, modulo P.

Sample Input 1

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

Sample output 1

1
0

Sample Input 2

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

Sample output 2

1
11

题意

N个节点M条边的图着k种颜色（其中M<=N+2),使得每条边连接的两个点是不同的颜色，求着色方案的数量。

这个问题本身是一个NP问题，应该用回溯法来解决。但是网上的这个模板改出来之后TLE，关了输入输出流同步之后还是TLE。我猜应该是这种方法写的...只是需要再优化。不然就是某个鬼畜的数学方法。

下面的超时代码：用邻接表c来表示一个无向连通图G=(V,E)。用整数1,2,…,m来表示m种不同的颜色。x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。

在回溯算法中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色方案，因此当前已找到的可m着色方案数sum增1。当i≤n时，当前扩展结点Z是解空间树中的一个内部结点。该结点有x[i]=1,2,…,m。对当前扩展结点Z的每一个儿子结点,由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。

TLE代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

#define ll long long

std::vector <int> c[50010];

ll point_color[5010];
ll cnt = 0;
ll n, m, u, v, g, p;

bool ok(int k) {
	for(int i = 1; i < k; i++){
		std::vector<int>::iterator result = find(c[k].begin( ), c[k].end( ), i); 
		if(!(result == c[k].end()) && point_color[i] == point_color[k]) {
			return 0;
		}
	}
	return 1;
}

void graphcolor(int n, int m) {
	for(int i = 1; i <= n; i++)
		point_color[i] = 0;
	int k = 1;
	while(k >= 1) {
		point_color[k] = point_color[k] + 1;
		while(point_color[k] <= m){
			if (ok(k)) {
				break;
			} else {
				point_color[k]=point_color[k]+1;
			}
		}
		if(point_color[k] <= m && k == n) {			
			cnt++;
			cnt %= p;
		}
		else if(point_color[k] <= m && k < n) {
			k = k + 1;
		} else {
			point_color[k] = 0;
			k = k - 1;
		}
	}
}


int main(int argc, char *argv[]) {
	std::ios::sync_with_stdio(false); 
	std::cin >> n >> g >> m >> p;
	int s, t;
	for(int i=1; i <= g ; i++) {
		std::cin >> s >> t;
		c[s].push_back(t);
		c[t].push_back(s);
	} 
	graphcolor(n, m);
	std::cout << cnt << std::endl;
	return 0;
}

##UPDATE 时隔一年之后群里问了这题，qls说是bell（6）暴力枚举三条非树边六个节点的颜色，然后树DP。 复习阶段 好像搞不动 先鸽着。