{"raw_statement":[{"iden":"statement","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"},{"iden":"входные данные","content":"В первой строке задано количество астронавтов N (2 ≤ N ≤ 105) и номер астронавта S (1 ≤ S ≤ N), поглощаемого в момент времени 0.В следующих N строках записаны пары чисел Li и Ri (1 ≤ Li, Ri ≤ N) — номера астронавтов, за которых астронавт номер i держится своей левой и правой руками соответственно."},{"iden":"выходные данные","content":"Выведите N чисел Ti, каждое из которых будет соответствовать моменту времени, когда астронавт под номером i будет поглощён Дырой, или равняться  - 1, если он останется невредим."},{"iden":"примеры","content":"Входные данные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 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"There are N astronauts. Each holds onto two other astronauts (one with each hand). At time 0, astronaut S is swallowed by a black hole. Every second after, the black hole swallows all astronauts who are directly holding onto someone already swallowed. Keep doing this until no more can be swallowed. For each astronaut, output the time they are swallowed, or -1 if they survive.","has_page_source":false}