#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5;
int dist[maxn+2][2];
vector<pair<int,int> >adj[maxn+2];
void dfs(int cur,int par){
for(auto x : adj[cur]){
if(x.first==par || x.second==1)continue;
dist[x.first][0]=dist[cur][0]+1;
dfs(x.first,cur);
}
}
void dfs2(int cur,int par){
for(auto x : adj[cur]){
if(x.first==par || x.second==0)continue;
dist[x.first][1]=dist[cur][1]+1;
dfs2(x.first,cur);
}
}
int siapa=0;
bool oke=false;
void solve(int cur,int par){
for(auto x : adj[cur]){
if(x.first==par || (dist[x.first][siapa]!=-1 && dist[x.first][siapa]<=dist[x.first][1-siapa]))continue;
if(x.second==siapa)continue;
// cout<<siapa<<" "<<cur<<endl;
solve(x.first,cur);
if(dist[x.first][siapa]==-1 && dist[cur][siapa]==-1){
oke=true;
}
}
}
signed main(){
memset(dist,-1,sizeof dist);
int n;
cin>>n;
int a,b;
cin>>a>>b;
bool blue=false;
bool red=false;
for(int q=1;q<n;q++){
int u,v;
cin>>u>>v;
string s;
cin>>s;
int col=0;
if(s=="crvena"){
col=1;
}
else if(s=="magenta"){
col=2;
}
adj[u].push_back({v,col});
adj[v].push_back({u,col});
if(col!=0 && (u==b || v==b))red=true;
if(col!=1 && ((u==a && v!=b) || (u!=b && v==a)))blue=true;
}
if(blue==false){
cout<<"Marin"<<endl;
return 0;
}
if(red==false){
cout<<"Paula"<<endl;
return 0;
}
dist[a][0]=dist[b][1]=0;
dfs(a,-1);
dfs2(b,-1);
if(dist[b][0]%2==1){
siapa=1;
}
if(siapa==0){
solve(a,-1);
if(oke){
cout<<"Magenta"<<endl;
}
else{
cout<<"Paula"<<endl;
}
}
else{
solve(b,-1);
if(oke){
cout<<"Magenta"<<endl;
}
else{
cout<<"Marin"<<endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |