Координаталық жазықтықта \(N\) қала бар. \(i\)-ші қала координаттарда орналасқан \((x_i, y_i)\) \(i\) және \(j\) қалалары арасындағы қашықтық мына формуламен есептеледі: \(\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}.\)

Барлық қалаларды дәл бір рет аралайтын \(N!\) түрлі жол бар. Жолдың ұзындығы — бірінші қаладан басталып, екінші, үшінші және соңғы қалаға дейінгі тікелей қашықтықтардың қосындысы. Барлық \(N!\) жолдардың орташа ұзындығын есептеңіз

Енгізу

Бірінші жолда бір бүтін сан \(N\) (\(2 \leq N \leq 8\)) — қалалар саны. Келесі \(N\) жолдың әрқайсысында екі бүтін сан \(x_i\) және \(y_i\) (\(-1000 \leq x_i, y_i \leq 1000\)) — \(i\)-ші қаланың координаттары.

Шығару

Барлық жолдардың орташа ұзындығын басып шығарыңыз. Сіздің жауабыңыз төрешінің жауабынан ең көп дегенде \(10^{-6}\) айырмашылықпен дұрыс болып саналады.

Бағалау жүйесі

Тапсырма 25 тесттен тұрады. Әрбір дұрыс орындалған тест үшін 4 балл беріледі.

Мысалдар бағаланбайды.

Мысалдар

Енгізу 1

3
0 0
1 0
0 1

Жауап 1

2.276142374915

Ескертпелер

Мүмкін болатын жолдар: \(1 \to 2 \to 3, \quad 1 \to 3 \to 2, \quad 2 \to 1 \to 3, \quad 2 \to 3 \to 1, \quad 3 \to 1 \to 2, \quad 3 \to 2 \to 1.\)