There are several ways to go about doing something like this.
1. The normalized relational way would be to add libraries for provinces and regions. This would be best for cases in which you either now or later will want to add data for provinces or regions, like statistics, populations, demographics, or whatever.
So, city would link to provinces 1-m, which would link to regions 1-m. The contacts library would link to cities 1-m and employ JavaScript fields to fetch the province and region through the links.
2. If you want to be able actually to select a city, a province, or a region from the same list, you could use a locations library that has them all; ideally no city and province or region would have the same name. In locations, you could link to locations in a couple of ways -- one for a province to a region and another for a city to a province. You might be able to figure out a way in contacts for JavaScript fields to detect the type of location and make things look both informative and valid.
3. You could probably do this using m-m links going the other way (from regions through provinces down to cities), but I'm not yet proficient doing this. I don't like the lists within entries nearly as much as I like lists of entries within libraries. Many more options for sorting, grouping, filtering, charting, and aggregation.
4. If you don't care to keep data about provinces or regions, you could just use radio buttons for those. The JavaScript fields in contacts could reach through the link to check those values and display whatever you'd like.