DWITE '08 R4 #3 - Secret party

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, January 2008, Problem 3

You are in charge of putting together a guest list for a party, but because of a typical teenage high-school drama situation, there is one particular person who you don't want to find out about the event (let alone invite). Being exceptionally paranoid, you want to take the safe side, and not invite anyone who is friends with friends of the above mentioned person (or direct friends of that person) (or that person). Luckily you have a computer, and there is a certain social website that will tell you everybody's friends.

You want to invite your direct friends only; unless they match the restriction above.

The input will contain 5 sets of input. First line is the number of relationships to follow, 1 \le n \le 100, followed by n lines in the person1 person2 format. Each relationship is considered mutual.

You always have an ID of 1; target person always has an ID of 2. All personIDs are integer values. There will always be IDs 1 and 2 in the sets.

The output will contain 5 lines - a space separated list of IDs of your direct friends to be invited, sorted in ascending order. In a special case where there is no one to invite, print none, without quotes.

Note: you only trust yourself to stay quiet. If, for some odd reason, you are friends with personID-2, that doesn't actually cancel the entire party.

Sample Input

2
1 2
1 3
2
1 3
3 2
3
1 3
3 4
4 2
4
1 3
3 4
4 5
5 2
8
1 3
1 4
3 2
5 6
7 1
2 8
8 9
9 1

Sample Output

3
none
none
3
4 7

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.