{"problem":{"name":"A. Сверхмассивная Черная Дыра","description":{"content":"Астронавты выполняют сложный трюк в космосе в рамках сверхсекретной миссии по заказу управления сверхсекретными миссиями Галактической Федерации. Каждый из них имеет две руки и держится каждой из них ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10136A"},"statements":[{"statement_type":"Markdown","content":"Астронавты выполняют сложный трюк в космосе в рамках сверхсекретной миссии по заказу управления сверхсекретными миссиями Галактической Федерации. Каждый из них имеет две руки и держится каждой из них независимо за ногу другого астронавта. Астронавт может держаться за двух разных астронавтов, обеими руками за одного, но не может держаться за свои ноги. При этом за ноги одного астронавта может держаться сколько угодно других.\n\nВнезапно в момент времени 0 из ниоткуда возникает Сверхмассивная Черная Дыра и поглощает астронавта с номером S. Каждую следующую секунду Дыра поглощает максимальное по включению множество не поглощённых ранее астронавтов, каждый из которых:\n\nКогда Дыра не может никого больше поглотить, она схлопывается и оставшиеся астронавты остаются невредимыми.\n\nДля каждого астронавта необходимо определить, будет ли он поглощён Сверхмассивной Черной Дырой в процессе выполнения миссии и, если да, то в какой момент времени.\n\nВ первой строке задано количество астронавтов N (2 ≤ N ≤ 105) и номер астронавта S (1 ≤ S ≤ N), поглощаемого в момент времени 0.\n\nВ следующих N строках записаны пары чисел Li и Ri (1 ≤ Li, Ri ≤ N) — номера астронавтов, за которых астронавт номер i держится своей левой и правой руками соответственно.\n\nВыведите N чисел Ti, каждое из которых будет соответствовать моменту времени, когда астронавт под номером i будет поглощён Дырой, или равняться  - 1, если он останется невредим.\n\n## Входные Данные\n\nВ первой строке задано количество астронавтов N (2 ≤ N ≤ 105) и номер астронавта S (1 ≤ S ≤ N), поглощаемого в момент времени 0.В следующих N строках записаны пары чисел Li и Ri (1 ≤ Li, Ri ≤ N) — номера астронавтов, за которых астронавт номер i держится своей левой и правой руками соответственно.\n\n## Выходные Данные\n\nВыведите N чисел Ti, каждое из которых будет соответствовать моменту времени, когда астронавт под номером i будет поглощён Дырой, или равняться  - 1, если он останется невредим.\n\n## Примеры\n\nВходные данные7 12 71 12 42 34 64 75 1Выходные данные0 1 2 2 3 3 3 Входные данные7 12 71 12 42 34 67 75 1Выходные данные0 1 2 2 -1 -1 -1 Входные данные3 12 31 11 2Выходные данные0 1 1 \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of astronauts.  \nLet $ S \\in \\{1, \\dots, N\\} $ be the astronaut absorbed at time $ 0 $.  \nLet $ G = (V, E) $ be a directed graph where $ V = \\{1, \\dots, N\\} $, and for each astronaut $ i $, there are two directed edges:  \n- $ i \\to L_i $ (left hand),  \n- $ i \\to R_i $ (right hand),  \nwhere $ L_i, R_i \\in \\{1, \\dots, N\\} $, and $ L_i \\ne i $, $ R_i \\ne i $ (no self-holds).\n\n**Constraints**  \n1. $ 2 \\le N \\le 10^5 $  \n2. $ 1 \\le L_i, R_i \\le N $, $ L_i \\ne i $, $ R_i \\ne i $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nFor each astronaut $ i \\in \\{1, \\dots, N\\} $, compute $ T_i \\in \\mathbb{Z}_{\\ge 0} \\cup \\{-1\\} $, where:  \n- $ T_S = 0 $,  \n- For $ t \\ge 1 $, $ T_i = t $ if astronaut $ i $ is absorbed at time $ t $, i.e., there exists an astronaut $ j $ with $ T_j = t-1 $ such that $ i \\to j \\in E $,  \n- $ T_i = -1 $ if no such path exists from $ S $ to $ i $ along the directed edges.\n\nEquivalently, $ T_i $ is the shortest directed path distance from $ S $ to $ i $ in $ G $, or $ -1 $ if no such path exists.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10136A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}