Degrees of Separation

Το κύριο μέσο κοινωνικοποίησης για τους μαθητές σήμερα είναι το Facebook. Υπάρχουν πολλές ενδιαφέρουσες υπολογιστικές ερωτήσεις που συνδέονται με το Facebook, όπως ο «βαθμός διαχωρισμού» («degree of separation») μεταξύ δύο ατόμων.

Για παράδειγμα, στο παρακάτω διάγραμμα, υπάρχουν πολλά διαφορετικά μονοπάτια που συνδέουν την Abby με τον Alberto. Μερικά από αυτά τα μονοπάτια είναι:

• Abby ~\to~ Zoey ~\to~ Alberto
• Abby ~\to~ Natalie ~\to~ Zoey ~\to~ Alberto
• Abby ~\to~ George ~\to~ Ali ~\to~ Kara ~\to~ Richardo ~\to~ Jeff ~\to~ Alberto

Το συντομότερο μονοπάτι μεταξύ της Abby και του Alberto αποτελείται από δύο βήματα (Abby ~\to~ Zoey και Zoey ~\to~ Alberto), οπότε λέμε ότι ο βαθμός διαχωρισμού είναι ~2~. Επιπλέον, θα λέγαμε πως ο Alberto είναι φίλος ενός φίλου της Abby.

Υποθέσετε μια αρχική διαμόρφωση του ποιος είναι φίλος με ποιον, όπως περιγράφεται στο παραπάνω διάγραμμα. Θα χρειαστεί να αποθηκεύσετε τις σχέσεις αυτές στο πρόγραμμά σας. Ωστόσο, αυτές οι σχέσεις μπορεί να αλλάξουν και το πρόγραμμά σας πρέπει να χειρίζεται αυτές τις αλλαγές. Συγκεκριμένα, μπορεί να ξεκινήσουν φιλίες, πιθανώς με νέα άτομα. Επίσης, κάποιες φιλίες μπορεί να τελειώσουν. Θα πρέπει να μπορείτε να βρίσκετε τους φίλους των φίλων και να καθορίζετε τον βαθμό διαχωρισμού μεταξύ δύο ατόμων.

Είσοδος/Έξοδος

Το πρόγραμμά σας θα διαβάζει έξι πιθανές εντολές, και η ενέργεια που θα πρέπει να εκτελεί περιγράφεται παρακάτω. Μπορείτε να υποθέσετε ότι τα ~x~ και ~y~ είναι ακέραιοι, με ~x \neq y~, ~x \ge 1~, ~y \ge 1~, ~x < 50~ και ~y < 50~. Μπορείτε επίσης να υποθέσετε ότι οι ~6~ εντολές (~i~, ~d~, ~n~, ~f~, ~s~, ~q~) εμφανίζονται μία ανά γραμμή και οι παράμετροι (μηδέν, ένας ή δύο ακέραιοι) εμφανίζονται και αυτές μία ανά γραμμή.

• ~i \times y~ – κάντε το άτομο ~x~ και το άτομο ~y~ φίλους. Αν είναι ήδη φίλοι, δεν χρειάζεται να γίνει καμία αλλαγή. Εάν είτε το ~x~ είτε το ~y~ είναι νέο άτομο, προσθέστε τα.
• ~d \times y~ – διαγράψτε τη φιλία μεταξύ του ατόμου ~x~ και του ατόμου ~y~.
• ~n \times~ – εξάγετε τον αριθμό των φίλων που έχει το άτομο ~x~.
• ~f \times~ – εξάγετε τον αριθμό «φίλοι φίλων» που έχει το άτομο ~x~. Παρατηρήστε ότι ο ~x~ και οι άμεσοι φίλοι του ~x~ δεν υπολογίζονται ως "φίλοι φίλων".
• ~s \times y~ – εξάγετε τον βαθμό διαχωρισμού μεταξύ των ~x~ και ~y~. Εάν δεν υπάρχει μονοπάτι από τον ~x~ στον ~y~, εξάγετε ~Not\;connected~.
• ~q~ – τερματισμός προγράμματος.

Παράδειγμα

input

i
20
10
i
20
9
n
20
f
20
s
20
6
q

output

2
3
4

Επεξήγηση του παραδείγματος:

Είσοδος	Έξοδος	Επεξήγηση
~i~ ~20~ ~10~	(no output)	Η εισαγωγή μιας φιλίας δεν παράγει έξοδο.
~i~ ~20~ ~9~	(no output)	Η εισαγωγή μιας φιλίας δεν παράγει έξοδο.
~n~ ~20~	~2~	Το άτομο ~20~ έχει δύο φίλους (τους ~10~ και ~9~)
~f~ ~20~	~3~	Οι φίλοι των φίλων του ~20~ είναι οι ~8~, ~11~, ~12~.
~s~ ~20~ ~6~	~4~	Το συντομότερο μονοπάτι είναι: ~20 \to 9 \to 8 \to 7 \to 6~.
~q~	(no output)	Το πρόγραμμα τερματίζει.