Учёный Иван Иванович изучает перевёрнутые родословные. Перевёрнутая родословная представляет собой набор людей, про каждого из которых известны либо оба его родителя, либо не известен ни один родитель. Кроме того, известно, что у всех людей из родословной есть ровно один ребёнок, кроме одного человека, у которого детей вовсе нет. Поэтому, если пронумеровать людей целыми числами от $$$1$$$ до $$$n$$$, то можно обозначить за $$$s_i$$$ номер ребёнка человека с номером $$$i$$$ и сказать, что $$$s_i = 0$$$ в случае, если у человека с номером $$$i$$$ детей нет.

Назовём человека $$$a$$$ предком человека $$$b$$$, если либо $$$a = b$$$, либо если у $$$a$$$ есть ребёнок, который является предком человека $$$b$$$. Это значит, что человек $$$a$$$ является предком для $$$a$$$, $$$s_a$$$, $$$s_{s_a}$$$ и так далее.

Будем считать, что произошёл перекос родословной с участием некоторого человека, если известны оба его родителя и количество известных предков одного из его родителей хотя бы вдвое больше, чем количество известных предков второго родителя.

Иван Иванович посчитал количество перекосов родословной и получил число $$$k$$$, но, конечно же, он делал это вручную и мог ошибиться. Помогите проверить Ивану Ивановичу его вычисления: скажите, существует ли родословная из $$$n$$$ людей с $$$k$$$ перекосами, и если существует, то приведите пример подобной родословной.