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
#include<bits/stdc++.h>

using namespace std;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) (int)(x).size()
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define REP(x, n) for(int x = 0; x < (n); x++)
#define FOR(x, b, e) for(int x = (b); x <= (e); x++)
#define FORD(x, b, e) for(int x = (b); x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)

typedef long long int LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MXN = 500010;
const int C = 262144;
const int INF = 1000000001;

VI G[MXN], GT[MXN];
int n, m, a, b;

//1 - dwukierunkowa
//0 - jednokierunkowa
int typ() {
	char z;
	FOR(i, 0, 1) {
		while(1) {
			z = getchar();
			if(z == '-' || z == '>')
				break;
		}
	}
	return z == '-';
}

void read() {
	scanf("%d %d %d %d", &n, &m, &a, &b);

	FOR(i, 1, m) {
		int x, y;
		scanf("%d", &x);
		int t = typ();
		scanf("%d", &y);
		GT[y].PB(x);
		if(t)
			GT[x].PB(y);
	}
}

int vis[MXN];

int calc(int mask) {
	queue<int> Q;
	FOR(i, 0, b - 1)
		if((1 << i) & mask) {
			Q.push(a + i + 1);			
			vis[a + i + 1] = mask + 1;
		}

	int cnt = 0;
	while(!Q.empty() ) {
		int w = Q.front();
		Q.pop();

		FOREACH(it, GT[w])
			if(vis[*it] != mask + 1) {
				vis[*it] = mask + 1;
				Q.push(*it);
			}
	}
	FOR(i, 1, a)
		if(vis[i] == mask + 1)
			cnt++;
	
	return cnt == a;
}

void test() {
	read();
	int res = 0;

	FOR(i, 0, (1 << b) - 1)
		res += calc(i);

	printf("%d\n", res);
}

int main() {
	int te = 1;
//	scanf("%d", &te);
	while(te--)
		test();
	return 0;
}