Problem H
Soccer Ball
A soccer ball by any other name: C60 (carbon 60), buckyball, buckminsterfullerene, truncated icosahedron, a 60-vertex graph of degree 3 with 12 black pentagons sharing edges with 20 white hexagons whose sides alternately meet pentagons and hexagons. Your task is to determine if a collection of straws can be glued together to form the seams of a soccer ball. The straws come from a kit in which, naturally, the ends have been labelled such that the 3 A’s are to be glued together, the 3 B’s are to be glued together, etc.. Since the alphabet does not have enough letters for all the 60 joints to be glued, we will use the integers 1 through 60.
Unfortunately, some of the straws may have been mislabeled. It is possible that numbers other than 1 to 60 appear. It is possible that both ends of a straw have the same label. It is possible that there are more or fewer than 3 occurrences of a label. Even if these conditions are avoided, it is possible that the soccer ball still can not be constructed, but we won’t worry about that here. The 3 tests to make are as follows:
-
$1 <= label <= 60$ for all straw labels.
-
Labels on either end of a straw are different for all straws.
-
Number of occurrences of each label is exactly 3 for all labels.
Input
There will be one line for each of the straws, each containing a pair of integer labels. The ordering of the straws is totally arbitrary and either end of the straw might be listed first.
Output
Confirm with "No" if the straws definitely can’t be assembled into a soccer ball by using the provided labelling. If the labelling passes the indicated tests, print "Yes", even though they don’t confirm it can be constructed.
Sample Input 1 | Sample Output 1 |
---|---|
1 2 2 3 3 4 4 5 5 1 1 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 6 2 9 3 12 4 15 5 18 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 57 58 58 59 59 60 7 22 8 25 10 26 11 29 13 30 14 33 16 34 17 37 19 38 21 40 23 42 24 44 27 45 28 47 31 48 32 50 35 51 36 53 39 54 41 55 43 57 46 58 49 59 52 60 56 60 |
Yes |