Custom rewrite rules on custom posttype

I’ve got a problem presented to me by a client which I can’t seem to fix. They have a WordPress website with a custom posttype ‘projects’

This custom posttype has a custom taxonomy ‘categories’

What they now have is two categories ‘men’ and ‘woman’ But the permalink to posts in both categories is /projects/my-project-title-1

What they would like is for the posts in the category ‘men’ to have a permalink like /men/my-project-title-1 and for ‘woman’ to have a permalink /woman/my-project-title-2.

Now I have found some tutorials online on how to remove the custom posttype slug from the url, but I have no clue on how to get the category in place.

I’m I trying to do something that’s not possible, or am I missing something else?