#include<bits/stdc++.h>
#include "abc.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;

// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1

#define lowbit(x) ((x)&-(x))

const int namelen = 19;
const int d = 16;
const int idlen = 11;
const int clrlen = 1;
const int M = 1024;

struct Divid
{
	vector<pii> seq;
	void divid2(int l,int r,int type)
	{
		if(l+1 == r) return;
		int mid = (l+r)>>1;
		for(int i=l,j=mid; i<mid; ++i, ++j)
		{
			if(type == 0)
				seq.emplace_back(i, j);
			else
				seq.emplace_back(j, i);
		}
		divid2(l,mid,type); divid2(mid,r,type);
	}
	
	void divid(int l,int r,int type)
	{
		if(l+1 == r) return;
		int mid = (l+r)>>1;
		divid(l,mid,1); divid(mid,r,0);
		divid2(l,r,type);
	}
	Divid(void)
	{
		divid(0, M, 0);
	}
	vector<int> get(vector<int> a)
	{
		while(a.size() != M)
			a.emplace_back(inf + (int)a.size());
		
		vector<int> res;
		for(auto t: seq)
		{
			int i = t.first, j = t.second;
			res.emplace_back(a[i] > a[j]);
			if(a[i] > a[j]) swap(a[i], a[j]);
		}
		
		return res;
	}
}ds;

int pw26(int k)
{
    int res = 1;
    while(k--) res *= 26;
    return res;
}

int encode_name(const char s[5])
{
    int len = strlen(s);
    int mask = 0;
    for(int i=0; i<len; ++i)
        mask = mask * 26 + s[i] - 'a';
    for(int i=1; i<len; ++i)
        mask += pw26(i);
    return mask;
}

int alice(const int n, const char s[][5], const unsigned short a[], bool out[])
{
	int cur = 0;
	
	vector<pii> vec;
	for(int i=0; i<n; ++i)
	{
		int mask = encode_name(s[i]);
		for(int j=0; j<namelen; ++j)
			out[cur++] = (mask >> j) & 1;
		vec.emplace_back(mask, a[i]);
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	
    for(int k=0; k<n; ++k)
    {
    	int mask = vec[k].first, ta = vec[k].second;
		for(int j=0; j<namelen; ++j)
			out[cur++] = (mask >> j) & 1;
		for(int j=0; j<d; ++j)
			out[cur++] = (ta >> j) & 1;
    }
    
    vector<int> tmp;
    for(int i=0; i<n; ++i)
    	tmp.emplace_back(-encode_name(s[i]));
    
	auto res = ds.get(tmp);
    for(auto t: res)
    	out[cur++] = t;
    
    return 1e5 - n;
}


int bob(const int m, const char us[][5], const char vs[][5], bool out[])
{
	vector<pii> vec(m);
	for(int i=0; i<m; ++i)
		vec[i] = {encode_name(us[i]), encode_name(vs[i])};
	sort(vec.begin(), vec.end());
	
	int cur = 0;
	for(int i=0; i<m; ++i)
	{
		int mask1 = vec[i].first;
		int mask2 = vec[i].second;
		for(int j=0; j<namelen; ++j)
			out[cur++] = (mask1 >> j) & 1;
		for(int j=0; j<namelen; ++j)
			out[cur++] = (mask2 >> j) & 1;
	}
	
	vector<int> tmp;
	for(int i=0; i<m; ++i)
		tmp.emplace_back(vec[i].second);
	
	auto res = ds.get(tmp);
	for(auto t: res)
		out[cur++] = t;
	
    return 1e5 - m;
}

//#define DEBUG

#ifdef DEBUG

namespace Grader
{
	const int MAXN = 700 + 5;
	const int MAXM = 1000 + 5;
	const int LEN = 2e7;
	
	int n,m;
	char s[MAXN][5], us[MAXM][5], vs[MAXM][5];
	unsigned short val[MAXN];
	
	bool a[LEN];
	int types[MAXN], uvs[MAXN][2], finans[MAXN][16];
	
	int len = 0;
	int push(int type,int u,int v)
	{
		if(len >= LEN)
		{
			printf("WA: Too many operations.");
			exit(0);
		}
		a[len] = (type >> (a[u] + 2 * a[v])) & 1;
		++len;
		return len - 1;
	}
}

#endif

namespace Circuit
{
	template<const size_t lenA, const size_t lenB>
	array<int, lenA + lenB> operator + (array<int, lenA> A, array<int, lenB> B)
	{
		array<int, lenA + lenB> res;
		for(int i=0; i<(int)lenA; ++i)
			res[i] = A[i];
		for(int i=0; i<(int)lenB; ++i)
			res[i+lenA] = B[i];
		return res;
	}
	
	using Tname = array<int,namelen>;
	using Tval = array<int,d>;
	using Tid = array<int,idlen>;
	using Tclr = array<int,clrlen>;
	
	int lena, lenb, *types;
	int (*uvs)[2], (*finans)[16];
	
	int anslen;
	int zero, one;
	
#ifdef DEBUG
	using Grader :: push;
#else
	int push(int type,int u,int v)
	{
		types[anslen] = type;
		uvs[anslen][0] = u;
		uvs[anslen][1] = v;
		++anslen;
		return anslen - 1;
	}
#endif
	
	int EQ(int u,int v)
	{
		return push(OP_EQUAL, u, v);
	}
	int AND(int u,int v)
	{
		return push(OP_AND, u, v);
	}
	int OR(int u,int v)
	{
		return push(OP_OR, u, v);
	}
	int XOR(int u,int v)
	{
		return push(OP_XOR, u, v);
	}
	
	template<const size_t len>
	array<int, len> add(array<int, len> A, array<int, len> B)
	{
		array<int,len> res;
		
		res[0] = XOR(A[0], B[0]);
		int lst = AND(A[0], B[0]);
		
		for(int i=1; i<(int)len; ++i)
		{
			res[i] = XOR(XOR(A[i], B[i]), lst);
			if(i != d-1)
				lst = OR(OR(AND(A[i], B[i]), AND(A[i], lst)), AND(B[i], lst));
		}
		
		return res;
	}
	
	template<const size_t len>
	int cmp_array(array<int, len> A, array<int, len> B)
	{
		int res = zero;
		for(int i=0; i<(int)len; ++i)
		{
			if(i == 0)
				res = push(OP_LESS, A[i], B[i]);
			else
				res = OR(push(2, res, XOR(A[i], B[i])), push(OP_LESS, A[i], B[i]));
		}
		return res;
	}
	
	template<const size_t len>
	void swap_array(int t, array<int, len> &A, array<int, len> &B)
	{
		for(int i=0; i<(int)len; ++i)
		{
			int cur = AND(t, XOR(A[i], B[i]));
			A[i] = XOR(A[i], cur);
			B[i] = XOR(B[i], cur);
		}
	}
	
	template<const size_t len>
	int cmp_swap_array(array<int, len> &A, array<int, len> &B)
	{
		array<int, len> mem;
		int res = zero;
		for(int i=0; i<(int)len; ++i)
		{
			mem[i] = XOR(A[i], B[i]);
			if(i == 0)
				res = push(OP_LESS, A[i], B[i]);
			else
				res = OR(push(2, res, mem[i]), push(OP_LESS, A[i], B[i]));
		}
		for(int i=0; i<(int)len; ++i)
		{
			int cur = AND(res, mem[i]);
			A[i] = XOR(A[i], cur);
			B[i] = XOR(B[i], cur);
		}
		return res;
	}
	
	template<const size_t len1, const size_t len2>
	int cmp_swap_array(array<int, len1> &A1, array<int, len2> &A2,
		array<int, len1> &B1, array<int, len2> &B2)
	{
		auto A3 = A1 + A2;
		auto B3 = B1 + B2;
		
		int res = cmp_swap_array(A3, B3);
		
		for(int i=0; i<int(len1 + len2); ++i)
			(i < (int)len1? A1[i]: A2[i - len1]) = A3[i];
		for(int i=0; i<int(len1 + len2); ++i)
			(i < (int)len1? B1[i]: B2[i - len1]) = B3[i];
		
		return res;
	}
	
	const int MAXN = M * 2;
	
	Tname us[MAXN], vs[MAXN];
	Tval val[MAXN];
	Tid id[MAXN];
	Tclr clr[MAXN];

#ifdef DEBUG
	
	void print(int i,bool flag_us,bool flag_vs,bool flag_val,bool flag_id,bool flag_clr)
	{
		printf("%3d: ",i);
		
		if(flag_us)
		{
			printf("us[");
			for(int j=namelen-1; j>=0; --j)
				printf("%d",(int)Grader :: a[us[i][j]]);
			printf("]  ");
		}
		
		if(flag_vs)
		{
			printf("vs[");
			for(int j=namelen-1; j>=0; --j)
				printf("%d",(int)Grader :: a[vs[i][j]]);
			printf("]  ");
		}
		
		if(flag_val)
		{
			printf("val[");
			for(int j=d-1; j>=0; --j)
				printf("%d",(int)Grader :: a[val[i][j]]);
			printf("]  ");
		}
		
		if(flag_id)
		{
			printf("id[");
			for(int j=idlen-1; j>=0; --j)
				printf("%d",(int)Grader :: a[id[i][j]]);
			printf("]  ");
		}
		
		if(flag_clr)
		{
			printf("clr[");
			for(int j=clrlen-1; j>=0; --j)
				printf("%d",(int)Grader :: a[clr[i][j]]);
			printf("]  ");
		}
		
		printf("\n");
	}
	
#endif
	
	function<int(int,int)> upd;
	vector< array<int,3> > mem;
	
	void divid2(int l,int r,int type)
	{
		if(l+1 == r) return;
		int mid = (l+r)>>1;
		
		for(int k=0; k<mid-l; ++k)
		{
			int i = l+k, j = mid+k;
			int t = type == 0? upd(j,i): upd(i,j);
			mem.push_back({i, j, t});
		}
		divid2(l,mid,type); divid2(mid,r,type);
	}
	
	void divid1(int l,int r,int type)
	{
		if(l+1 == r) return;
		int mid = (l+r)>>1;
		divid1(l,mid,1); divid1(mid,r,0);
		divid2(l,r,type);
	}
}

int circuit(const int _lena, const int _lenb, int _types[], int _uvs[][2], int _finans[][16])
{
	using namespace Circuit;
	
	lena = _lena; lenb = _lenb; types = _types; uvs = _uvs; finans = _finans;
	
	anslen = lena + lenb;
	zero = push(OP_ZERO, 0, 0);
	one = push(OP_ONE, 0, 0);
	
	int n = 1e5 - lena;
	int m = 1e5 - lenb;
	
	int tot = 0;
	{
		int cur = 0;
		
		cur += namelen * n;
		for(int t=0; t<n; ++t)
		{
			int i = tot++;
			
			for(int j=0; j<namelen; ++j)
				us[i][j] = cur++;
			for(int j=0; j<namelen; ++j)
				vs[i][j] = j<d? cur++: one;
			clr[i][0] = one;
		}
		
		cur = lena;
		for(int t=0; t<m; ++t)
		{
			int i = tot++;
			
			for(int j=0; j<namelen; ++j)
				us[i][j] = cur++;
			for(int j=0; j<namelen; ++j)
				vs[i][j] = cur++;
			clr[i][0] = zero;
		}
		
		while(tot != MAXN)
		{
			int i = tot++;
			
			for(int j=0; j<namelen; ++j)
				us[i][j] = one, vs[i][j] = one;
			clr[i][0] = zero;
		}
	}
	
//	printf("Stage 0:\n");
//	for(int i=0; i<tot; ++i)
//		print(i, 1, 1, 0, 0, 1);
	
	upd = [&] (int i,int j)
	{
		int t = cmp_swap_array(clr[i], us[i], clr[j], us[j]);
		swap_array(t, vs[i], vs[j]);
		return t;
	};
	mem.clear();
	divid2(0, tot, 0);
	reverse(mem.begin(), mem.end());
	
//	printf("%d\n",anslen);
	
//	printf("\nStage 1:\n");
//	for(int i=0; i<tot; ++i)
//		print(i, 1, 1, 0, 0, 1);
	
	for(int i=tot-1; i>=0; --i)
	{
		int t = clr[i][0];
		for(int j=0; j<d; ++j)
			val[i][j] = AND(t, vs[i][j]);
		
		if(i+1 == tot) continue;
		
		t = one;
		for(int j=0; j<namelen; ++j)
			t = AND(t, EQ(us[i][j], us[i+1][j]));
		
		for(int j=0; j<d; ++j)
			val[i][j] = OR(val[i][j], AND(t, val[i+1][j]));
	}
	
	for(auto cmem: mem)
	{
		int u = cmem[0], v = cmem[1], t = cmem[2];
		swap_array(t, vs[u], vs[v]);
		swap_array(t, val[u], val[v]);
	}
	
	{
		int cur = n * namelen;
		for(int i=0; i<n; ++i)
		{
			for(int j=0; j<namelen; ++j)
				vs[i][j] = cur++;
			cur += d;
			
			for(int j=0; j<d; ++j)
				val[i][j] = zero;
			clr[i][0] = one;
		}
		for(int i=n; i<tot; ++i)
			clr[i][0] = zero; 
	}
	
//	printf("\nStage 2:\n");
//	for(int i=0; i<tot; ++i)
//		print(i, 0, 1, 1, 0, 1);
	
	mem.clear();
	for(int k=0; k<(int)ds.seq.size(); ++k)
	{
		int i = ds.seq[k].first, j = ds.seq[k].second;
		int t = n * (namelen * 2 + d) + k;
		
		mem.push_back({i, j, t});
	}
	
//	printf("\nStage 2.8:\n");
//	for(int i=0; i<tot; ++i)
//		print(i, 0, 1, 1, 0, 1);
	
	for(int k=0; k<(int)ds.seq.size(); ++k)
	{
		int i = ds.seq[k].first + n, j = ds.seq[k].second + n;
		int t = lena + m * namelen * 2 + k;
		
		swap_array(t, vs[i], vs[j]);
		swap_array(t, val[i], val[j]);
		
//		mem.push_back({i, j, t});
	}
	
//	printf("\nStage 2.9:\n");
//	for(int i=0; i<tot; ++i)
//		print(i, 0, 1, 1, 0, 1);
	
	upd = [&] (int i,int j)
	{
		int t = cmp_swap_array(clr[i], vs[i], clr[j], vs[j]);
		swap_array(t, val[i], val[j]);
		return t;
	};
	divid2(0, tot, 0);
	reverse(mem.begin(), mem.end());
	
//	printf("%d\n",anslen);
	
//	printf("\nStage 3:\n");
//	for(int i=0; i<tot; ++i)
//		print(i, 0, 1, 1, 0, 1);
	
	for(int i=1; i<tot; ++i)
	{
		int t = one;
		for(int j=0; j<namelen; ++j)
			t = AND(t, EQ(vs[i][j], vs[i-1][j]));
		
		Tval tmp;
		for(int j=0; j<d; ++j)
			tmp[j] = AND(t, val[i-1][j]);
		
		val[i] = add(val[i], tmp);
	}
	
//	printf("%d\n",anslen); 
	
	for(auto cmem: mem)
	{
		int u = cmem[0], v = cmem[1], t = cmem[2];
		swap_array(t, val[u], val[v]);
	}
	
//	printf("%d\n",anslen);
	
	for(int i=0; i<n; ++i)
		for(int j=0; j<d; ++j)
			finans[i][j] = val[i][j];
	
	return anslen;
}

#ifdef DEBUG

int main(void)
{
	using namespace Grader;
	
	cin >> n >> m;
	for(int i=0; i<n; ++i)
		cin >> s[i] >> val[i];
	for(int i=0; i<m; ++i)
		cin >> us[i] >> vs[i];
	
	int lena = alice(n, s, val, a);
	int lenb = bob(m, us, vs, a + lena);
	
	Grader :: len = lena + lenb;
	
	circuit(lena, lenb, types, uvs, finans);
}

#endif