D. Код доторх саад

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сүүлийн үед ФОС кодонд ноцтой саад тулгарчээ. F компанийн удирдлага гэмт хэрэгтэнг олон шийтгэхийг хүсчээ. Түүний тулд зохион байгуулалттай уулзалт зохиов. Хэлэлцүүлэг "Хэн кодыг саадтай болгосон бэ?" сэдэвтэй. $n$ кодер бүр '$x$ эсвэл $y$ үүнийг хийсэн!' гэсэн хариу өгчээ.

Компанийн удирдлага хоёр сэжигтэнг дуудан уулзана. Мэдээж тэрээр кодеруудын бодлыг авч үзэх хэрэгтэй. Тиймээс $n$ кодеруудын ядаж $p$ нь удирдлагатай санал нэгтэй байх ёстой. Кодер бүрийн саналын ядаж нэг нь удирдлагын сонгосон сэжигтэн байвал тухайн кодерийг санал нэгтэй байна гэж тооцно. F компанийн удирдлага хоёр сэжигтэнг хэчнээн янзаар сонгож болох вэ?

Ямар нэгэн кодер удирдлагад сэжигтнээр сонгогдсон байсан ч уг кодер нөгөө сэжигтэнг сэжиглэж байгаа бол удирдлагатай санал нэг байгаа гэж тооцогдох юм.

Оролт

Эхний мөрөнд кодеруудын тоо болон хамгийн бага санал нэгдэх ёстой тоог илэрхийлэх $n$ ба $p$ $(3 ≤ n ≤ 3*10^{5}; 0 ≤ p ≤ n)$ тоонууд өгөгдөнө.

Дараагийн $n$ мөр бүрт $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n)$ гэсэн хоёр бүхэл тоо байн ба энэ нь $i$ дэх кодерийн хариу юм. $x_{i} ≠ i,  y_{i} ≠ i,  x_{i} ≠ y_{i}$ байх болно.

Гаралт

Боломжит хоёр сэжигтнүүдийн тоог хэвлэ. Сэжигтнүүдийн хувьд эрэмбэ хамаарахгүйг анхаарна уу. Өөрөөр хэлбэл $(1, 2)$ ба $(2, 1)$ нь ижил хосд тооцогдоно.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4 2
2 3
1 4
1 4
2 1
Гаралт
6
Оролт
8 6
5 6
5 7
5 8
6 2
2 1
7 3
1 3
1 4
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...