Астронавты выполняют сложный трюк в космосе в рамках сверхсекретной миссии по заказу управления сверхсекретными миссиями Галактической Федерации. Каждый из них имеет две руки и держится каждой из них независимо за ногу другого астронавта. Астронавт может держаться за двух разных астронавтов, обеими руками за одного, но не может держаться за свои ноги. При этом за ноги одного астронавта может держаться сколько угодно других.
Внезапно в момент времени 0 из ниоткуда возникает Сверхмассивная Черная Дыра и поглощает астронавта с номером S. Каждую следующую секунду Дыра поглощает максимальное по включению множество не поглощённых ранее астронавтов, каждый из которых:
- обязательно держался хотя бы за одного астронавта, поглощённого ранее (на предыдущих секундах);
- может держаться за астронавтов из поглощаемого в данную секунду множества;
- не держится за остальных астронавтов.
Когда Дыра не может никого больше поглотить, она схлопывается и оставшиеся астронавты остаются невредимыми.
Для каждого астронавта необходимо определить, будет ли он поглощён Сверхмассивной Черной Дырой в процессе выполнения миссии и, если да, то в какой момент времени.
В первой строке задано количество астронавтов N (2 ≤ N ≤ 105) и номер астронавта S (1 ≤ S ≤ N), поглощаемого в момент времени 0.
В следующих N строках записаны пары чисел Li и Ri (1 ≤ Li, Ri ≤ N) — номера астронавтов, за которых астронавт номер i держится своей левой и правой руками соответственно.
Выведите N чисел Ti, каждое из которых будет соответствовать моменту времени, когда астронавт под номером i будет поглощён Дырой, или равняться - 1, если он останется невредим.
7 1
2 7
1 1
2 4
2 3
4 6
4 7
5 1
0 1 2 2 3 3 3
7 1
2 7
1 1
2 4
2 3
4 6
7 7
5 1
0 1 2 2 -1 -1 -1
3 1
2 3
1 1
1 2
0 1 1
