{"problem":{"name":"K. Birdwatching","description":{"content":"Kiara does not know the real graph $cal(G)$ governing the flight of these birds but, in her previous field study, Kiara has collected data from the journey of many birds. Using this, she has devised a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10250K"},"statements":[{"statement_type":"Markdown","content":"Kiara does not know the real graph $cal(G)$ governing the flight of these birds but, in her previous field study, Kiara has collected data from the journey of many birds. Using this, she has devised a graph $cal(P)$ explaining how they move. Kiara has spent so much time watching them that she is confident that if a bird can fly directly from $a$ to $b$, then she has witnessed at least one such occurrence. However, it is possible that a bird flew from $a$ to $b$ to $c$ but she only witnessed the stops $a$ and $c$ and then added $(a, c)$ to $cal(P)$. It is also possible that a bird flew from $a$ to $b$ to $c$ to $d$ and she only witnessed $a$ and $d$, and added $(a, d)$ to $cal(P)$ , etc. To sum up, she knows that $cal(P)$ contains all the edges of $cal(G)$ and that $cal(P)$ might contain some other edges $(a, b)$ for which there is a path from $a$ to $b$ in $cal(G)$ (note that $cal(P)$ might not contain all such edges).\n\nFor her next field study, Kiara has decided to install her base next to a given tree $T$. To be warned of the arrival of birds on $T$, she would also like to install detectors on the trees where the birds can come from (i.e. the trees $T '$ such that there is an edge ( $T ', T$) in $cal(G)$ ). As detectors are not cheap, she only wants to install detectors on the trees $T '$ for which she is sure that $(T ', T)$ belongs to $cal(G)$.\n\nKiara is sure that an edge $(a, b)$ belongs to $cal(G)$ when $(a, b)$ is an edge of $cal(P)$ and all the paths in $cal(P)$ starting from $a$ and ending in $b$ use the edge $(a, b)$. Kiara asks you to compute the set $S (T)$ of trees $T '$ for which she is sure that $(T ', T)$ is an edge of $cal(G)$.\n\nThe input describes the graph $cal(P)$. The first line contains three space-separated integers $N$, $M$, and $T$: $N$ is the number of nodes of $cal(P)$, $M$ is the number of edges of $P$ and $T$ is the node corresponding to the tree on which Kiara will install her base.\n\nThe next $M$ lines describe the edges of the graph $cal(P)$. Each contains two space-separated integers $a$ and $b$ ($0 <= a$, $b < N$ and $a != b$) stating that $(a, b) in cal(P)$ . It is guaranteed that the same pair $(a, b)$ will not appear twice.\n\n*Limits* \n\nYour output should describe the set $S (T)$. The first line should contain an integer $L$, which is the number of nodes in $S (T)$, followed by $L$ lines, each containing a different element of $S (T)$. The elements of $S (T)$ should be printed in increasing order, with one element per line.\n\n*Sample Explanation 1*\n\nThe graph corresponding to this example is depicted below. The node 1 belongs to $S (2)$ because the (only) path from 1 to 2 uses (1, 2). The node 0 does not belong to $S (2)$ because the path $0 arrow.r 1 arrow.r 2$ does not use the edge (0, 2). \n\n*Sample Explanation 2*\n\nThe graph corresponding to this example is depicted below. For the same reason as in Sample 1, the node 0 does not belong to $S (2)$ while 1 does. The nodes 3 and 5 do not belong to $S (2)$ because we do not have edges (3, 2) or (5, 2). Finally 4 belongs to $S (2)$ because all paths from 4 to 2 use the edge (4, 2). \n\n## Input\n\nThe input describes the graph $cal(P)$. The first line contains three space-separated integers $N$, $M$, and $T$: $N$ is the number of nodes of $cal(P)$, $M$ is the number of edges of $P$ and $T$ is the node corresponding to the tree on which Kiara will install her base.The next $M$ lines describe the edges of the graph $cal(P)$. Each contains two space-separated integers $a$ and $b$ ($0 <= a$, $b < N$ and $a != b$) stating that $(a, b) in cal(P)$ . It is guaranteed that the same pair $(a, b)$ will not appear twice.*Limits*   $1 <= N, M <= 100000$;  $0 <= T < N$. \n\n## Output\n\nYour output should describe the set $S (T)$. The first line should contain an integer $L$, which is the number of nodes in $S (T)$, followed by $L$ lines, each containing a different element of $S (T)$. The elements of $S (T)$ should be printed in increasing order, with one element per line.\n\n[samples]\n\n## Note\n\n*Sample Explanation 1*The graph corresponding to this example is depicted below. The node 1 belongs to $S (2)$ because the (only) path from 1 to 2 uses (1, 2). The node 0 does not belong to $S (2)$ because the path $0 arrow.r 1 arrow.r 2$ does not use the edge (0, 2).   *Sample Explanation 2*The graph corresponding to this example is depicted below. For the same reason as in Sample 1, the node 0 does not belong to $S (2)$ while 1 does. The nodes 3 and 5 do not belong to $S (2)$ because we do not have edges (3, 2) or (5, 2). Finally 4 belongs to $S (2)$ because all paths from 4 to 2 use the edge (4, 2).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ j, g, c, p \\in \\mathbb{Z}^+ $ denote the grid dimensions, required separation distance, and number of shoe pairs, respectively.\n\n**Constraints**  \n1. $ 1 \\le t \\le 10^5 $  \n2. For each test case:  \n   - $ 1 \\le j, g, c, p \\le 10^{18} $  \n\n**Objective**  \nDetermine whether it is possible to place $ 2p $ distinct shoes on a $ j \\times g $ grid such that:  \n- Each shoe is paired with exactly one other shoe (forming $ p $ disjoint pairs).  \n- For each pair, the two shoes are separated by exactly $ c $ cells in one of the four cardinal directions (up, down, left, right).  \n- No cell contains more than one shoe.  \n\nEquivalently:  \nIs there a set of $ p $ disjoint pairs of cells $ \\{(x_1, y_1), (x_2, y_2)\\} $ in the grid $ \\{1, \\dots, j\\} \\times \\{1, \\dots, g\\} $, such that for each pair, $ |x_1 - x_2| + |y_1 - y_2| = c $ and $ \\min(|x_1 - x_2|, |y_1 - y_2|) = 0 $?  \n\nThat is, each pair lies on the same row or same column, with Manhattan distance exactly $ c $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10250K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}