Ostov ağaclarının qurulması

G qeyri-yonlü tam sadə qrafını nəzərdən keçirək, burada $n$ təpə var. G qrafının təpələri $1$-dən $n$-ə qədər nömrələnmişdir. Xüsusilə, hər bir fərqli təpə cütü bir qeyri-yonlü kənarla birləşdirilib, buna görə qraf dəqiq olaraq n \cdot (n - 1) / 2 kənar ehtiva edir.

Sizə bu qraf G-nin n - 3 kənarından ibarət olan E çoxluğu verilib. Daha dəqiq desək, sizə $x$ və $y$ adlı iki massiv verilib, hər biri n - 3 elementdən ibarətdir. Hər bir uyğun $i$ üçün (x_i, y_i) E-də olan kənarlardan biridir.

G qrafının skelet ağacı - bu qrafın n - 1 kənarından ibarət olan alt çoxluqdur ki, bu kənarlar bütün $n$ təpələri birləşdirir. Skelet ağacının kənarları həqiqətən G qrafının alt qrafı olan və bütün təpələri əhatə edən bir ağac təşkil edir.

Biz E verilmiş çoxluğunun bütün kənarlarını ehtiva edən skelet ağacları ilə maraqlanırıq. Belə skelet ağaclarının sayını $987654323$ modulu ilə tapın. İki skelet ağacı fərqlidir, əgər G qrafında bir kənar mövcuddursa, o birinə aiddir, amma digərinə aid deyil.

Çıxış

Skelet ağaclarının sayını $987654323$ modulu ilə çıxarın.