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
//Marcin Knapik, PA2019, Dzień 4, Zadanie "Wyspa"[A]
//złożoność O(2^n)

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

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

int a, b, n, m;

#define pb push_back

const int N = 1e6+7;
bool odw[N];
int gdzie[N];
int akt;

vector<int> dotk;
vector<vector<int>> G(N);
void dfs(int start){
	if(start > a && start <= a + b)
		gdzie[akt] |= (1<<(start - a - 1));
	dotk.pb(start);
	odw[start] = 1;
	for(auto&u:G[start])
		if(!odw[u])
			dfs(u);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> a >> b;

	for(int i = 0; i < m; i++){
		int x, y;
		string p;
		cin >> x >> p >> y;

		if(p == "->"){
			G[x].pb(y);
		}
		else{
			G[x].pb(y);
			G[y].pb(x);
		}
	}

	for(int i = 1; i <= a; i++){
		akt = i;
		dfs(i);
		for(auto&u:dotk)
			odw[u] = 0;
		dotk.clear();
	}

	int ans = 0;

	for(int i = 0 ; i < (1<<b); i++){
		bool ok = 1;
		for(int j = 1; j <= a; j++)
			if(!(i&gdzie[j]))
				ok = 0;
		if(ok)
			ans++;
	}

	cout << ans << '\n';
}