Sponsorun poçtu

Siz hamınız yeni il yarışları ilə bağlı “Sponsorun vədi” məsələsini xatırlayırsınız. Bu məsələdə qarşıya qoyulan problemi qısaca yada salırıq: yarışdan sonra sponsor qaliblərə prizlər göndərmək istəyir.

Lakin poçt sistemi müasir olmadığından prizi iştirakçıların hamısına çatdırmaq mümkün deyil. Konkret olaraq, ölkədə $1$-dən $n$-dək nömrələnmiş $n$ sayda poçt şöbələri var. Sponsor prizi s nömrəli poçt şöbəsindən yola salır. Öz aralarında əlaqəsi olan, yəni hansı poçt şöbələri arasında poçtların göndərilməsi mümkündürsə, bu poçt şöbələri cütlüyü də məlumdur.

Yeni yarışlardan əvvəl sponsor prizlərin çatdırılması imkanlarının təminatını qabaqcadan sığortalamağı qərara alır. Bunun üçün sponsor bəzi poçt şöbələri cütlükləri arasında öz vəsaiti hesabına yeni əlaqələrin qurulmasına da hazırdır.

Sizin vəzifəniz — sponsor ən az nə qədər yeni sayda əlaqələr yaratmalıdır ki, yarışdan sonra prizləri bütün iştirakçılara onların harada yaşamasından və hansı poçt şöbəsinin xidmətindən istifadə etməsindən asılı olmayaraq çatdıra bilsin.

Giriş verilənləri

Birinci sətirdə üç ədəd-poçt şöbələrinin $n(1\le n\le 10^5)$ sayı, sponsorun istifadə etdiyi poçt şöbəsinin $s(1\le s\le n)$ nömrəsi və aralarında əlaqə olan poçt şöbələri cütlüklərinin $k(0\le k\le 10^5)$ sayı verilir.

Sonrakı $k$ sayda sətrin hər birində iki $a$ və $b$ ədədi — aralarında poçt daşımaları həyata keçirilən şöbələrin nömrələri yazılır $(a$ və $b[1;n]$ intervalından olan müxtəlif ədədlərdir). Bütün $(a,b)$ cütlükləri giriş faylında müxtəlifdir.

Çıxış verilənləri

Yeganə ədəd-poçtu $s$ şöbəsindən istənilən şöbəyə çatdırmaq üçün yaradılması zəruri olan ən az mümkün yeni əlaqələrin sayı.

Nümunələr