{"problem":{"name":"G. Get Higher and Higher","description":{"content":"_The rivalry of Lowie and B21 have history. That's how the HNOI Civil War was found._ Both are challenged to a contest called: \"Who Can Get His Tree Higher?\". As straightforward as it sound: Lowie an","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10227G"},"statements":[{"statement_type":"Markdown","content":"_The rivalry of Lowie and B21 have history. That's how the HNOI Civil War was found._\n\nBoth are challenged to a contest called: \"Who Can Get His Tree Higher?\". As straightforward as it sound: Lowie and B21 bring their own trees and get to pick a node of choice as the root, the one who gets his tree to have the greater height of wins the the contest.\n\nTo revise: A _tree_ is a connected bidirectional graph with N vertices and N-1 edges. The height of one tree is the greatest distance from the root to one of its leaves. A distance between two nodes on a tree is the number of nodes that are on the simple path between those two nodes.\n\nB21 is a master of trees. He knows how to make the optimal move to make the height of his tree as great as possible by choosing the best root. Meanwhile, Lowie doesn't know it. Lowie will choose a random node to be the root of his tree.\n\nNevertheless, B21's tree is still way smaller than Lowie's one, so even with an optimal move, B21 would still cannot win this contest. Your job is to show B21 if he still stand any chance to win this contest. A draw is a draw, which means neither player won, and they will find another contest to compete in.\n\nThe first line contains an integer: $N$ ($1 <= N <= 10^5$) - number of nodes in B21's tree.\n\nThe next $N$ lines, each contains $2$ integers: $u$ and $v$ ($1 <= u, v <= N$) - denotes that there is an edge connects node $u$ and node $v$ in B21's tree.\n\nThe next line contains an integer: $M$ ($N < M <= 2 * 10^5$) - number of nodes in Lowie's tree.\n\nThe next $M$ lines, each contains $2$ integers: $u$ and $v$ ($1 <= u, v <= N$) - denotes that there is an edge connects node $u$ and node $v$ in Lowie's tree.\n\nIf B21 stand a chance to win, output \"_GGEZ_\". Otherwise, output \"_FF_\".\n\nIn both sample tests, B21 will obtain the maximum height of his tree if he chooses node $4$ as the root of his tree:\n\nThe height of this tree is now $4$.\n\nIn the first example, B21 will win if Lowie choose node $1$ as the root:\n\nIn the second example, even after Lowie made the worst choice of root, the contest would still be a draw, that means B21 cannot win in any way:\n\n## Input\n\nThe first line contains an integer: $N$ ($1 <= N <= 10^5$) - number of nodes in B21's tree.The next $N$ lines, each contains $2$ integers: $u$ and $v$ ($1 <= u, v <= N$) - denotes that there is an edge connects node $u$ and node $v$ in B21's tree.The next line contains an integer: $M$ ($N < M <= 2 * 10^5$) - number of nodes in Lowie's tree.The next $M$ lines, each contains $2$ integers: $u$ and $v$ ($1 <= u, v <= N$) - denotes that there is an edge connects node $u$ and node $v$ in Lowie's tree.\n\n## Output\n\nIf B21 stand a chance to win, output \"_GGEZ_\". Otherwise, output \"_FF_\".\n\n[samples]\n\n## Note\n\nIn both sample tests, B21 will obtain the maximum height of his tree if he chooses node $4$ as the root of his tree:  The height of this tree is now $4$.In the first example, B21 will win if Lowie choose node $1$ as the root:  In the second example, even after Lowie made the worst choice of root, the contest would still be a draw, that means B21 cannot win in any way:","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T_B = (V_B, E_B) $ be B21’s tree with $ |V_B| = N $, and $ T_L = (V_L, E_L) $ be Lowie’s tree with $ |V_L| = M $, where $ N < M $.  \n\nLet $ h_B = \\max_{r \\in V_B} \\text{height}(T_B, r) $ be the **diameter-based height** of B21’s tree, i.e., the maximum possible height when choosing the optimal root (equivalent to half the diameter rounded up).  \nLet $ h_L^{\\min} = \\min_{r \\in V_L} \\text{height}(T_L, r) $ be the **minimum possible height** of Lowie’s tree over all root choices.  \n\n**Constraints**  \n1. $ 1 \\le N \\le 10^5 $  \n2. $ N < M \\le 2 \\cdot 10^5 $  \n3. Both $ T_B $ and $ T_L $ are trees (connected, acyclic, undirected).  \n\n**Objective**  \nDetermine if $ h_B > h_L^{\\min} $.  \n- If true, output \"_GGEZ_\".  \n- Otherwise, output \"_FF_\".  \n\n**Note**: The height between two nodes is defined as the number of nodes on the simple path between them (inclusive). Thus, the height of a tree rooted at $ r $ is the maximum number of nodes along any root-to-leaf path.  \nThe optimal root for maximizing height in a tree is a center of the diameter; the maximum height is $ \\left\\lceil \\frac{D}{2} \\right\\rceil + 1 $, where $ D $ is the number of nodes in the longest path (diameter).  \nThe minimum height over all roots in a tree is achieved when the root is a center of the diameter: $ \\left\\lfloor \\frac{D}{2} \\right\\rfloor + 1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10227G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}