Advertisement
Promi1707052

Untitled

Sep 21st, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.29 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<math.h>
  4. #include<vector>
  5. #include<set>
  6. #include<queue>
  7. #include<algorithm>
  8. #include<cstring> //for memset
  9. using namespace std;
  10.  
  11. #define lli int long long
  12. #define ull unsigned long long
  13. #define ld long double
  14. #define pi acos(-1)
  15. #define pb push_back
  16. #define pbk pop_back
  17. #define mp make_pair
  18. #define ff first
  19. #define ss second
  20. #define pii pair<int,int>
  21. #define gcd(a,b) __gcd(a,b)
  22. #define lcm(a,b) (a/gcd(a,b))*b
  23. #define READ freopen("in.txt","r",stdin);
  24. #define WRITE freopen("outer.txt","w",stdout);
  25. //#define sort(t) sort(t.begin(),t.end())
  26. #define mem(a,b) memset(a,b,sizeof a)
  27. #define sf scanf
  28. #define pf printf
  29. #define cs(p) printf("Case %d: ", ++(p))
  30. #define dist(ax,ay,bx,by) sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
  31. #define MM 100003
  32. #define inf 10000000000000000+7
  33. #define M 1000000002
  34. #define MINI -1000000003
  35. //const int fx[]={+1,-1,+0,+0};
  36. //const int fy[]={+0,+0,+1,-1};
  37. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
  38. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
  39.  
  40. //#define for(i,a,n) for(int i=a;i<n;i++)
  41. //it=myset.find(20);
  42. //int a[8]= {0,0,-1,1,-1,1,-1,1};
  43. //int b[8]= {-1,1,0,0,-1,1,1 ,-1};
  44. vector<int>v1[100005],v2[100005];
  45. bool vis[100005],vis2[100005];
  46. int y,dis[100005],dis2[100005];
  47.  
  48. int bfs1(int s,int p)
  49. {
  50. vis[s]=1;
  51. queue<int>q;
  52. q.push(s);
  53. if(p==1)
  54. dis[s]=0;
  55. while(!q.empty())
  56. {
  57. int u=q.front();
  58. q.pop();
  59. y=u;
  60. //cout<<u<<endl;
  61. for(int i=0;i<v1[u].size();i++)
  62. {
  63. int r=v1[u][i];
  64. if(vis[r]==0)
  65. {
  66. if(p==1)
  67. dis[r]=dis[u]+1;
  68. vis[r]=1;
  69. q.push(r);
  70. }
  71. }
  72. }
  73. return y;
  74. }
  75. int bfs2(int s,int p)
  76. {
  77. vis2[s]=1;
  78. queue<int>q;
  79. q.push(s);
  80. if(p==1)
  81. dis2[s]=0;
  82. while(!q.empty())
  83. {
  84. int u=q.front();
  85. q.pop();
  86. y=u;
  87. for(int i=0;i<v2[u].size();i++)
  88. {
  89. int r=v2[u][i];
  90. if(vis2[r]==0)
  91. {
  92. if(p==1)
  93. dis2[r]=dis2[u]+1;
  94. vis2[r]=1;
  95. q.push(r);
  96. }
  97. }
  98. }
  99. return y;
  100. }
  101.  
  102. int main()
  103. {
  104. int i,j,k,n,u,v,m;
  105. cin>>n;
  106. for(i=0;i<n-1;i++)
  107. {
  108. cin>>u>>v;
  109. v1[u].pb(v);
  110. v1[v].pb(u);
  111. }
  112. cin>>m;
  113. for(i=0;i<m-1;i++)
  114. {
  115. cin>>u>>v;
  116. v2[u].pb(v);
  117. v2[v].pb(u);
  118. }
  119. int ly=bfs1(1,0);
  120. memset(vis,0,sizeof vis);
  121. int ly2=bfs1(ly,1);
  122. int ll=bfs2(1,0);
  123. memset(vis2,0,sizeof vis2);
  124. int ll2=bfs2(ll,1);
  125. int pr1=dis[ly2]+1;
  126. int pr2=(dis2[ll2]/2)+1;
  127. if(pr2<pr1)
  128. cout<<"GGEZ"<<endl;
  129. else cout<<"FF"<<endl;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement