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
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<vector> #include<algorithm>
typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std;
inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; }
int n,g[1020]; struct E{ int u,v,w,nex; }e[1020]; int ansu=0,ansv=0; int f[1020]; void dfs(int d1,int d2,int d3,int l1,int l2){ if(ansu&&ansv) return; int n4=0,n7=0; if(l1==4) n4++; else if(l1==7) n7++; if(l2==4) n4++; else if(l2==7) n7++; for(int i=g[d3];i>0;i=e[i].nex){ if(f[e[i].v]) continue; if(e[i].w==4) n4++; else if(e[i].w==7) n7++; if(n4&&n7&&n4+n7==3){ ansu=1,ansv=1; if(n4==2){
cout<<d1<<' '<<e[i].v<<' '<<"7"<<endl; } else{ cout<<d1<<' '<<e[i].v<<' '<<"4"<<endl; } return; } if(e[i].w==4) n4--; else if(e[i].w==7) n7--; f[e[i].v]=1; dfs(d2,d3,e[i].v,l2,e[i].w); f[e[i].v]=0; } } int main(){ io_opt; cin>>n; int x,y,z; for(int i=1;i<=n-1;i++){ cin>>x>>y>>z; e[i]=(E){x,y,z,g[x]};g[x]=i; e[i+n-1]=(E){y,x,z,g[y]};g[y]=i+n-1; }
for(int i=1;i<=n;i++){ ansu=ansv=0; f[i]=1; dfs(0,0,i,0,0); f[i]=0; if((ansu&&ansv)){ return 0; } } cout<<"-1"<<endl; return 0; }
|