#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 1e5+5;
const int LG = 18;
int anc[N][LG];
int n,n0,n1;
struct edge{
int v,color;
};
vector<edge> adj[N];
int d[3][N];
void dfs(int u,int p){
anc[u][0]=p;
for(int lg=1;lg<LG;lg++) anc[u][lg]=anc[anc[u][lg-1]][lg-1];
for(edge e:adj[u]){
int v=e.v;
if(v == p) continue;
d[2][v]=d[2][u]+1;
d[1][v]=d[1][u] + (e.color != 0);
d[0][v]=d[0][u] + (e.color != 1);
dfs(v,u);
}
}
int lca(int u,int v){
if(d[2][u] < d[2][v]) swap(u,v);
int dis=d[2][u]-d[2][v];
for(int lg=LG-1;lg>=0;lg--){
if((dis&(1<<lg))>0) u=anc[u][lg];
}
if(u == v) return u;
for(int lg=LG-1;lg>=0;lg--){
if(anc[u][lg] != anc[v][lg]){
u=anc[u][lg];
v=anc[v][lg];
}
}
return anc[u][0];
}
int dist(int u,int v,int c){
int lc=lca(u,v);
return d[c][u]+d[c][v]-2*d[c][lc];
}
int findlc(int a,int b,int c){
vector<int> lc;
lc.push_back(lca(a,b));
lc.push_back(lca(a,c));
lc.push_back(lca(b,c));
sort(lc.begin(),lc.end(),[&](int i,int j){
return d[2][i] > d[2][j];
});
return lc[0];
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
if(fopen("text.inp","r")){
freopen("text.inp","r",stdin);
}
cin>>n;
cin>>n0>>n1;
for(int i=1;i<n;i++){
int u,v,c;
string s;
cin>>u>>v>>s;
if(s == "plava") c=0;
else if(s == "crvena") c=1;
else c=2;
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
dfs(1,0);
auto safe_for_Marin = [&](int x) {
// Paula không tới được, Marin tới được
if (!(dist(n0,x,0) != dist(n0,x,2) && dist(n1,x,1) == dist(n1,x,2))) return false;
int lc = findlc(x, n0, n1);
if(dist(n0,lc,0) != dist(n0,lc,2)) return true; // Paula ko tới được ngã rẽ
if(dist(n0,lc,2) > dist(n1,lc,2)) return true; // Marin tới ngã rẽ trước
return false;
};
// Tạo hàm kiểm tra 1 đỉnh x có an toàn cho Paula (chống lại Marin) không:
auto safe_for_Paula = [&](int x) {
if (!(dist(n0,x,0) == dist(n0,x,2) && dist(n1,x,1) != dist(n1,x,2))) return false;
int lc = findlc(x, n0, n1);
if(dist(n1,lc,1) != dist(n1,lc,2)) return true;
if(dist(n1,lc,2) >= dist(n0,lc,2)) return true;
return false;
};
if ((dist(n0, n1, 2)) % 2 == 0) {
// Paula rượt Marin. Marin cần CẠNH an toàn để hòa.
bool has = false;
for (int u = 1; u <= n; u++) {
if (has) break;
for (edge e : adj[u]) {
int v = e.v;
// Nếu cạnh này Marin đi được (color != 0) và cả 2 đầu u, v đều an toàn cho Marin
if (e.color != 0 && safe_for_Marin(u) && safe_for_Marin(v)) {
has = true;
break;
}
}
}
if (has) cout << "Magenta\n";
else cout << "Paula\n";
} else {
// Marin rượt Paula. Paula cần CẠNH an toàn để hòa.
bool has = false;
for (int u = 1; u <= n; u++) {
if (has) break;
for (edge e : adj[u]) {
int v = e.v;
// Nếu cạnh này Paula đi được (color != 1) và cả 2 đầu u, v đều an toàn cho Paula
if (e.color != 1 && safe_for_Paula(u) && safe_for_Paula(v)) {
has = true;
break;
}
}
}
if (has) cout << "Magenta\n";
else cout << "Marin\n";
}
}
