Solution

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 100005;

typedef pair<int, int> pii;

map<string, int> col = {
    {"plava", 0},
    {"crvena", 1},
    {"magenta", 2}
};

string name[3] = {"Paula", "Marin", "Magenta"};

int n;
int path_len, chased;

int s[2];
int dist[maxn][2];

bool can_move[2];

vector<pii> e[maxn];

void dfs(int x, int who, int p) {
    for (int i = 0; i < (int)e[x].size(); i++) {
        int y = e[x][i].first;
        int c = e[x][i].second;
        if (y == p)
            continue;
        if (y == s[who ^ 1])
            path_len = dist[x][who] + 1;
        if (c != (who ^ 1)) {
            dist[y][who] = dist[x][who] + 1;
            dfs(y, who, x);
        }
    }
}

bool escape(int x, int p) {
    bool esc = 0;
    for (int i = 0; i < (int)e[x].size(); i++) {
        int y = e[x][i].first;
        int c = e[x][i].second;
        if (y == p || c == (chased ^ 1) || dist[y][chased ^ 1] != -1 && dist[y][chased] >= dist[y][chased ^ 1])
            continue;
        if (dist[x][chased ^ 1] == -1 && dist[y][chased ^ 1] == -1) 
            return 1;  
        esc |= escape(y, x);
    }
    return esc;
}

void outp(int x) {
    cout << name[x] << endl;
    exit(0);
}

int main() {   
    ios::sync_with_stdio(false);
    cin >> n >> s[0] >> s[1];
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        string tmp;
        cin >> x >> y >> tmp;
        int c = col[tmp];
        e[x].push_back(pii(y, c));
        e[y].push_back(pii(x, c));
        if (c != 1 && (x == s[0] && y != s[1] || y == s[0] && x != s[1]))
            can_move[0] = 1;
        if (c != 0 && (x == s[1] || y == s[1]))
            can_move[1] = 1;
    }
    if (!can_move[0]) 
        outp(1);
    if (!can_move[1])
        outp(0); 
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < 2; i++) {
        dist[s[i]][i] = 0;
        dfs(s[i], i, -1);
    }
    chased = (path_len + 1) % 2;
    if (escape(s[chased], -1))
        outp(2);
    outp(chased ^ 1);
    return 0;
}