Маша собирается принять участие в шоу талантов, проводимом университетом, в котором она учится. Она хочет поразить публику множеством разных фокусов!

Для одного из своих фокусов она использует $$$n$$$ шариков, один из которых — особенный. Сначала Маша размещает шарики в ряд таким образом, чтобы особенный шарик находился на позиции $$$k$$$ (позиции пронумерованы от $$$1$$$ до $$$n$$$ слева направо). После этого она выполняет $$$m$$$ обменов: во время $$$i$$$-го обмена она выбирает шарик на позиции $$$x_i$$$ и шарик на позиции $$$y_i$$$ и меняет их местами.

Чтобы обмануть аудиторию, Маша иногда делает фальшивые действия — имитирует, что начинает обмен, но не выполняет его (но аудитории кажется, что он выполнен). Нет никаких ограничений на то, какие обмены Маша должна имитировать или должна действительно выполнить — например, она может имитировать все обмены или выполнить все из них.

Чтобы фокус работал идеально, особенный шарик должен оказаться в определенной позиции, но Маша еще не определилась, какая из позиций идеальна. Поскольку имитировать обмены сложно, для каждой позиции она хочет знать минимальное количество обменов, которое она должна сымитировать, чтобы особенный шарик оказался там.

К сожалению, Маша — волшебница, а не математик и не программист. Поэтому ей нужна ваша помощь!