408717: GYM103270 G Doggo Daycare

Betty owns a dog daycare service. Part of her advertised duties involves taking the dogs out on a walk. However, she only has $$$3$$$ leashes for her $$$5$$$ dogs. She knows from experience that if she takes out $$$2$$$ dogs who are friendly with each other and $$$1$$$ who neither of the other two like, then the dogs will be sad after the walk. The only way for the dogs to be happy is if all $$$3$$$ of the dogs like each other or if none of the dogs like each other (in that case, one dog won't feel left out). As Betty was thinking about how to make such a group, a friend of hers noted that with $$$6$$$ dogs, it is always possible to find a group of $$$3$$$ dogs who all like each other or all dislike each other. Given a list of $$$n$$$ pairs of dog friendships, see if it is possible for Betty to form a group of $$$3$$$ who will all be happy at the end of the walk.

Note: When it says all $$$3$$$ dogs like each other, it must mean that there is a dog friendship between each pair of dogs in the group of $$$3$$$ (i.e. if the group was A, B, C then there must be friendship between A and B, A and C, and B and C). Similar property must hold except there shouldn't be any pair-wise friendships in the group for all $$$3$$$ to dislike each other. Assume that if a friendship is not listed between two dogs, it means that the two dogs don't like each other.

The first line contains a single integer $$$n$$$ which is the number of dog friendships among the $$$5$$$ dogs ($$$1 \leq n \leq 10$$$).

The following $$$n$$$ lines will each contain two space-separated integers $$$a_{i}$$$ and $$$b_{i}$$$ which are two dogs that are friends (each dog is represented by a unique number between $$$1$$$ and $$$5$$$). You are guaranteed that $$$a_{i} \neq b_{i}$$$ and $$$1 \leq a_{i}, b_{i} \leq 5$$$. Also, a friendship between dog A and B is symmetrical (B is also friends with A) so you will never have a repeat/symmetrical friendship listed.

Print Happy Doggos! if such a group of $$$3$$$ exists or Sad Doggos... if no such group exists.

4
1 3
2 3
1 4
5 3

Happy Doggos!

5
1 2
2 3
3 4
4 5
5 1

Sad Doggos...