გზათა სისტემა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: GEOI, 2010, დასკვნითი, XI-XII კლასი


  ქვეყანაში, რომელშიც 1-დან N-მდე გადანომრილი N რაოდენობის ქალაქია, ხელისუფლებას სურს მათი დამაკავშირებელი გზათა ისეთი სისტემის შექმნა, რომ თითოეული მათგანი ზუსტად ორ სხვა ქალაქთან იყოს დაკავშირებული ორმხრივი გზებით. თუმცა, საკვირველია, მაგრამ გზათა ზოგიერთი ასეთი სისტემის შემთხვევაში შეიძლება ყოველთვის არ იყოს შესაძლებელი თითოეული ქალაქიდან სხვა ნებისმიერ ქალაქში მოხვედრა. მიუხედავად ამისა, მათ მტკიცედ აქვთ გადაწყვეტილი სწორედ ასეთი სისტემის შექმნა და მხოლოდ ის აინტერესებთ, თუ ამის გაკეთების რამდენი განსხვავებული ვარიანტი იარსებებს.
 
    დაწერეთ პროგრამა, რომელიც ქალაქთა მოცემული რაოდენობისათვის დაადგენს, თუ გზათა რამდენი ისეთი განსხვავებული სისტემა არსებობს, რომლებიც ზემოთ მოცემულ პირობას აკმაყოფილებს. 
გზათა ორი სისტემა განსხვავებულია, თუ პირველი მათგანის შიგნით არის ერთი მაინც გზა i და j ქალაქთა წყვილს შორის ისეთი, რომელიც არ გვხვდება მეორე სისტემაში.
 
    შესატანი მონაცემები: შესატან მონაცემთა ფაილის პირველ სტრიქონში მოცემულია ერთი ნატურალური N რიცხვი (3 ≤ N ≤ 100) ქვეყანაში ქალაქთა რაოდენობა.
 
    გამოსატანი მონაცემები: გამოსატან მონაცემთა ფაილის ერთადერთ სტრიქონში უნდა ჩაიწეროს გზათა განსხვავებული სისტემების რაოდენობა.
 
 



მაგალითები

შესატანი მონაცემები
4 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება
შესატანი მონაცემები
6 დაკოპირება
გამოსატანი მონაცემები
70 დაკოპირება