Secure and deterministic MACs which are not strongly secure? One of the practice problems I was given for an exam that I'm preparing for is as follows:


  Let $\Pi$ be a secure, deterministic MAC that uses canonical
  verification. Show how to construct a MAC $\Pi'$ that is secure and
  deterministic but is not strongly secure.


In my book, it says that if a MAC uses canonical verification, then it is a strong MAC. This seems to suggest that $\Pi'$ should not use canonical verification.

By the definition of a strongly secure MAC, for our construction, an adversary should be able to generate a new valid tag on an existing message-tag-pair that it has seen before. However, if the MAC is deterministic, doesn't that mean that each unique message only has one valid tag?

How do I approach such a construction? If all deterministic secure MACs can use canonical verification, and all secure MACs that use canonical verification are strongly secure, then doesn't that mean that all deterministic MACs are strongly secure?
A deterministic MAC can use canonical verification, but it doesn't have to.
Thus, the question allows you to create deterministic MAC without canonical verification. How can you use this to your advantage?

Hint 1: 


   What if you add some auxiliary (constant) bit to the output of the  tagging algorithm of $\Pi$. How can you define the verification algorithm of $\Pi'$ to still be UF-CMA secure but not SUF-CMA secure?


Hint 2:   


   This question is very similar to another question given here: Difference between INT-CTXT and INT-PTXT