Tıxanma aşkarlayıcı

Şəhər məclisi, xüsusilə dalanlarda yol nişanlarının yerləşdirilməsini təkmilləşdirmək qərarına gəlib. Sizə yol xəritəsi təqdim edilib və dalanları göstərmək üçün nişanların harada yerləşdiriləcəyini müəyyən etməlisiniz. Məqsəd mümkün qədər az sayda nişan istifadə etməkdir.

Yol xəritəsi, iki tərəfli hərəkət olan küçələrlə birləşən kəsişmələr dəstini təmsil edir. Aşağıdakı qayda dalan nişanlarının tam yerləşdirilməsini təsvir edir. $S$ küçəsini, $x$ yerini başqa bir yerə birləşdirən küçə kimi nəzərdən keçirin. Əgər $x$-dən $S$-ə daxil olduqdan sonra, dönmə etmədən $x$-ə qayıtmaq mümkün deyilsə, $S$-ə giriş dalan olur. Dönmə - dərhal istiqaməti dəyişdirən $180$ dərəcəlik dönmədir.

Xərcləri azaltmaq üçün artıq dalan nişanlarını quraşdırmamağa qərar verdiniz, aşağıdakı qayda ilə göstərildiyi kimi. $x$-girişində dalan nişanı olan $S$ küçəsini və $y$-girişində dalan nişanı olan başqa $T$ küçəsini nəzərdən keçirin. Əgər $x$-dən $S$-ə daxil olduqdan sonra dönmə etmədən $y$-ə çatmaq və $T$-ə daxil olmaq mümkündürsə, $T$ küçəsinin $y$-girişindəki dalan nişanı artıqdır. Şəkil E.1-dəki nümunələrə baxın.

Şəkil E.1: Artıq olmayan dalan nişanlarının yerləşdirilməsini göstərən nümunə ilə giriş məlumatlarının təsviri.

Çıxış

Birinci sətirdə quraşdırılmış dalan nişanlarının sayı $k$-ni göstərin. Növbəti $k$ sətirin hər birində $v$ və $w$ tam ədədlərini göstərin, bu da $v$ kəsişməsini $v$ və $w$ kəsişmələrini birləşdirən küçəyə girişdə dalan nişanı quraşdırılmalı olduğunu göstərir. Dalan nişanlarını təsvir edən sətirlər $v$-nin artan sırasına görə, bərabər qiymətlərdə isə $w$-nin artan sırasına görə sıralanmalıdır.